什么是二分图？如何判断一个图是不是二分图？

简化版

二分图是指：顶点能分成两个组，使得每条边都连接两个不同组的顶点（组内没有边）。判定用染色法：DFS 或 BFS 遍历，给起点染一种颜色，它的邻居必须染另一种颜色，一路染下去；如果发现某条边的两个端点颜色相同，就不是二分图。等价结论：一个图是二分图 ⟺ 它不含奇数长度的环。

详细版

定义：图的顶点集能划分成 A、B 两个不相交子集，所有边都是「一端在 A、一端在 B」，A 内部和 B 内部都没有边。

染色判定（两种颜色）：

int[] color;   // 0 未染, 1 / 2 两种颜色
boolean isBipartite(int n, List<List<Integer>> adj) {
    color = new int[n];
    for (int i = 0; i < n; i++)
        if (color[i] == 0 && !dfs(i, 1, adj)) return false; // 图可能不连通，每个都试
    return true;
}
boolean dfs(int u, int c, List<List<Integer>> adj) {
    color[u] = c;
    for (int v : adj.get(u)) {
        if (color[v] == 0) {
            if (!dfs(v, 3 - c, adj)) return false;  // 邻居染另一色（1↔2）
        } else if (color[v] == c) {
            return false;                            // 邻居同色 → 冲突，非二分图
        }
    }
    return true;
}

3 - c 在 1 和 2 之间切换（给邻居染相反色）。发现相邻同色即失败。

完整版教学

一、二分图是什么、有什么用

二分图的直观理解是「两拨人，连线只在两拨之间」。典型例子：学生和课程（谁选了哪门课）、员工和任务（谁能做哪个任务）、男生和女生（配对）。这类「两类实体之间的关系」天然是二分图。二分图上有很多经典问题：最大匹配（匈牙利算法、最大二分匹配）、任务分配等，所以先判断「是不是二分图」是基础。

二、染色法的核心思想

判定二分图 = 尝试用两种颜色给所有顶点染色，要求相邻顶点颜色不同。如果能成功染完（没有任何一条边两端同色），说明能按颜色把顶点分成两组、边都跨组 → 是二分图；如果染色过程中出现「一条边两端被迫同色」的矛盾 → 不是。

用 DFS 或 BFS 遍历：给当前点染一种色，强制它所有邻居染另一种色，递归下去。一旦发现某个邻居已经染了和当前点相同的颜色，矛盾，判定失败。

三、别忘了图可能不连通

一个易错点：图可能有多个连通分量。所以要对每个还没染色的顶点都启动一次染色（外层循环），否则会漏掉孤立的部分。每个连通分量独立判定，全部都是二分图才算整个图是二分图。

四、等价结论：无奇数环

有一个重要定理：一个图是二分图，当且仅当它不包含长度为奇数的环。

直觉：沿着环交替染色 1、2、1、2……如果环长是偶数，绕一圈回到起点颜色正好一致，无矛盾；如果环长是奇数，绕一圈回来颜色会和起点冲突（染色矛盾）。所以奇环是二分图的「天敌」。这个结论让你能从「有没有奇环」的角度快速判断。

五、复杂度与其它解法

染色法（DFS/BFS）：O(V + E)，遍历一遍。
并查集解法：也可以用并查集——把每个点的「敌人（应在对面组）」合并，如果发现一个点和它的敌人被并到了一起，就矛盾。染色法更直观常用。

六、常见误区与追问

考点	正确口径
定义	点集可分成两部分，每条边都跨集合
判定	用两种颜色给相邻点染不同色
等价条件	不存在奇数环

for each unvisited node:
  color[start] = 0
  BFS/DFS:
    if neighbor uncolored: color = 1 - color[cur]
    else if color same: not bipartite

二分图染色失败，本质就是发现了一条要求两个端点同色的奇数环约束。

误区：只从 0 号点开始染色就够了。 图可能不连通，必须遍历所有未访问节点作为新起点。
误区：有环就不是二分图。 偶数环仍然是二分图，真正破坏二分性的是奇数环。
误区：二分图只适用于无向图。 经典二分图定义多用于无向图；若是有向边，通常先明确是否忽略方向。
追问：为什么相邻点必须异色？ 两部分集合内部不能有边，边只能连接两个集合，所以相邻点必须分到不同侧。
追问：DFS 和 BFS 哪个更好？ 都可以，核心是颜色约束传播；BFS 更像层层扩散，DFS 代码也很直接。
追问：复杂度是多少？ 邻接表表示下时间 O(V+E)，空间 O(V) 保存颜色和队列/递归栈。

七、加强记忆

二分图 = 顶点分两组、边只跨组连接（组内无边）。判定用染色法：DFS/BFS 给相邻点染不同色（3-c 交替），发现相邻同色即非二分图；O(V+E)。注意图可能不连通，要对每个未染色点都启动。等价结论：二分图 ⟺ 不含奇数长度的环（偶环染色能自洽、奇环必冲突）。应用：二分匹配、任务分配。也可用并查集判定。

简化版

详细版