判断二分图

怎么判？换个说法：把「分两拨」翻译成「染两种颜色」：相邻的点必须不同色。只要能染成功，就是二分图。

为什么不用枚举：颜色像多米诺骨牌：第一个点一定色，后面全被推着走。所以根本不用试 2 的 n 次方种染法，顺着边「染过去」就行。

优解：染色法（BFS）：走一遍图，边走边染、相邻就反色；一旦遇到「该反色却已经同色」的边，说明劈不开，直接 false。下面一帧染一个点、一帧查一条边地演给你看。

例一 · 全部未染：先把例一画好：四个点围成方框，四条边 0–1、1–2、2–3、3–0。一开始谁都没染色。

起点 0 染 A · 入队：随便挑起点 0，给它染上颜色 A（蓝）放进队列。它将带动整个连通块的染色。

取出 0 · 准备看邻居：从队列取出 0（紫色高亮 = 正在处理）。它是 A，接下来逐条看它的边，邻居都该染成反色 B。

查边 0–1 · 1 没染：看边 0–1（高亮）。1 还没染，染成反色 B（绿）入队。0 蓝、1 绿，这条边合法。

查边 0–3 · 3 没染：再看 0 的另一条边 3–0（高亮）。3 也没染，同样染成 B（绿）入队。0 的两条边都跨了色，合法。

取出 1 · 准备看邻居：取出 1（B/绿，紫色高亮）。0 退回普通蓝。1 是 B，它的邻居该染成 A。

查边 1–0 · 已染，比一下：看边 1–0（高亮）。0 已经染过了，就比一下颜色：0 是 A、1 是 B，不同色，合法，跳过。

查边 1–2 · 2 没染：看边 1–2（高亮）。2 还没染，染成 A（蓝）入队。此刻分组成形：A 拨 = {0,2}，B 拨 = {1,3}。

1 处理完 · 放回队列看下一个：1 的两条边都查完、没撞色，它处理完毕（变绿）。四个点这下都染上了色，队列里还剩 3、2 等着核对。

取出 3 · 全是老边：取出 3（B/绿，高亮）。它连 0（A）和 2（A），两条边都已染好（高亮）且颜色都和 3 不同，全合法，无需新染。

取出 2 · 队列将空：取出 2（A/蓝，高亮）。它连 1、3，都是 B，和 2 不同色，合法。队列空了，整张图染完都没撞过色。

例一收工 · 是二分图：全染完且从没撞色：A 拨 = {0,2}（蓝），B 拨 = {1,3}（绿）。能干净劈成两拨 → true。

反例 · 藏着三角形：看反例 graph=[[1,2,3],[0,2],[0,1,3],[0,2]]。这里 0、1、2 互相都连，形成一个三角形——它会让染色撞墙。

起点 0 染 A · 入队：同样从 0 起步，染A（蓝）入队。它连着 1、2、3 三个点，等会儿出队就会把它们都逼成 B。

取出 0 · 查边 0–1：出队 0（高亮），看边 0–1。1 没染，染 B（绿）入队。0 蓝 1 绿，这条边目前合法。

查边 0–2 · 2 染 B：再看边 0–2。2 也没染，同样染 B（绿）入队。注意：1 和 2 之间也有一条边，而它俩现在都是绿！

查边 0–3 · 3 染 B：0 的最后一条边 0–3：3 没染，染 B（绿）入队。0 的三个邻居全是 B——隐患已经埋下。

取出 1 · 查边 1–2：出队 1（B/绿），查它的边 1–2（高亮）。可 2 也是 B（绿）！相邻两点同色，这条边劈不开，立刻返回 false。

本质：奇数环：记住这个结论：一张图是二分图，当且仅当它没有奇数长度的环。三角形就是最小的奇环，所以反例必然 false。

套路模板：凡是「分两组 / 相邻不同 / 站队对立」的题，都能套这个两色染色模板。

易错实演 · 不连通图：这张图分两块：{0,1} 和 {2,3,4}。从 0 跑只染好了上面一块，第二块 2、3、4 还全是灰的。

外层 for 接着跑第二块：外层 for 走到没染的 2，重启一次 BFS 把第二块也染好（2、4 蓝，3 绿）。这就是为什么必须遍历每个点。

边界三连：无边永远 true；最小的反例是三角形。记住边越密越容易出奇环。

面试追问：面试常追问 DFS/BFS/并查集三种写法，以及怎么顺手把两组成员输出。