一、什么是二分图
二分图（Bipartite Graph） 是一种特殊的无向图，其顶点可以分成两个互不相交的集合 A 和 B，使得每条边都连接 A 中的一个顶点和 B 中的一个顶点。
等价定义：图中不含奇数长度的环。
Mermaid · 渲染中（下方为源码）
graph LR A1[A1] --- B1[B1] A1 --- B2[B2] A2[A2] --- B1 A2 --- B3[B3] A3[A3] --- B2
左边 {A1, A2, A3}，右边 {B1, B2, B3}，所有边跨两侧。
二、判断二分图（染色法）
用 BFS/DFS 给节点染两种颜色，相邻节点颜色不同：
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n]; // 0=未染色, 1=红, -1=蓝
for (int i = 0; i < n; i++) {
if (color[i] != 0) continue;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
color[i] = 1;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (color[v] == 0) {
color[v] = -color[u];
queue.offer(v);
} else if (color[v] == color[u]) {
return false; // 同色相邻 → 不是二分图
}
}
}
}
return true;
}