785. 判断二分图
题目描述
有一张 n 个节点的无向图，节点编号为 0 到 n - 1。输入二维数组 graph，graph[u] 列出与节点 u 相连的所有节点。
图中没有自环和重复边；若 v 在 graph[u] 中，则 u 也在 graph[v] 中。图不一定连通。
如果能把全部节点分到两个集合里，使每条边的两个端点分别位于不同集合，这张图就是二分图。是二分图返回 true，否则返回 false。
示例 1
输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false
解释：节点 0、1、2 两两相连构成三角形，无法分成两组。
示例 2
输入：graph = [[1,3],[0,2],[1,3],[0,2]] 输出：true
解释：可以分成 {0,2} 和 {1,3} 两组。
数据范围
graph.length == n1 <= n <= 1000 <= graph[u].length < n0 <= graph[u][i] <= n - 1graph[u]不含u本身。graph[u]中的值各不相同。- 若
v在graph[u]中，则u也在graph[v]中。
解题思路：广度优先搜索染色
二分图等价于能用两种颜色给节点染色、且相邻节点颜色不同。对每个还没染色的节点作为起点做 BFS：起点染 0，出队节点 u 的每个邻居 v，如果未染色就染成与 u 相反的颜色并入队；如果已染色且与 u 同色，说明出现了奇数环，返回 false。所有连通块都染完没有冲突，返回 true。
为什么正确
已染色的节点中，任何一条已检查过的边两端颜色都不同。
复杂度分析
时间 O(V+E)，每个节点入队一次、每条边检查两次；空间 O(V)。
易错点
图可能不连通，必须对每个未染色节点都启动一次 BFS，只从节点 0 出发会漏掉其他连通块里的奇数环。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
color = [-1] * n
for start in range(n):
if color[start] != -1:
continue
color[start] = 0
queue = collections.deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = color[u] ^ 1
queue.append(v)
elif color[v] == color[u]:
return False
return Trueclass Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int start = 0; start < n; start++) {
if (color[start] != -1) {
continue;
}
color[start] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.offer(start);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.offer(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
return true;
}
}class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> color(n, -1);
for (int start = 0; start < n; start++) {
if (color[start] != -1) {
continue;
}
color[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
return true;
}
};func isBipartite(graph [][]int) bool {
n := len(graph)
color := make([]int, n)
for i := range color {
color[i] = -1
}
for start := 0; start < n; start++ {
if color[start] != -1 {
continue
}
color[start] = 0
queue := []int{start}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
for _, v := range graph[u] {
if color[v] == -1 {
color[v] = color[u] ^ 1
queue = append(queue, v)
} else if color[v] == color[u] {
return false
}
}
}
}
return true
}var isBipartite = function(graph) {
const n = graph.length;
const color = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) {
continue;
}
color[start] = 0;
const queue = [start];
let head = 0;
while (head < queue.length) {
const u = queue[head++];
for (const v of graph[u]) {
if (color[v] === -1) {
color[v] = color[u] ^ 1;
queue.push(v);
} else if (color[v] === color[u]) {
return false;
}
}
}
}
return true;
};function isBipartite(graph: number[][]): boolean {
const n = graph.length;
const color: number[] = new Array(n).fill(-1);
for (let start = 0; start < n; start++) {
if (color[start] !== -1) {
continue;
}
color[start] = 0;
const queue = [start];
let head = 0;
while (head < queue.length) {
const u = queue[head++];
for (const v of graph[u]) {
if (color[v] === -1) {
color[v] = color[u] ^ 1;
queue.push(v);
} else if (color[v] === color[u]) {
return false;
}
}
}
}
return true;
}其他解法
染色法（广度或深度优先）是判断二分图的标准做法；并查集把“邻居同侧”变成集合合并，适合在线加边。
解法 2：并查集 时间 O((V + E) · α(V))，空间 O(V)
二分图中每个点的所有邻居都必须在另一侧，即邻居之间彼此同侧。对每个点 u，把它的所有邻居合并到第一个邻居所在的集合；合并前先检查 u 和邻居是否已经在同一集合，如果是，说明有一条边连着同侧的两点，不是二分图。
不需要显式染色和队列，边可以任意顺序处理，适合边动态加入的场景。但想法不如染色直观，也不能直接给出两侧的划分。
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
parent = list(range(len(graph)))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, nbrs in enumerate(graph):
for v in nbrs:
if find(u) == find(v):
return False
parent[find(v)] = find(nbrs[0])
return Trueclass Solution {
int[] parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public boolean isBipartite(int[][] graph) {
int n = graph.length;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int u = 0; u < n; u++) {
for (int v : graph[u]) {
if (find(u) == find(v)) return false;
parent[find(v)] = find(graph[u][0]);
}
}
return true;
}
}class Solution {
public:
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
for (int u = 0; u < n; u++) {
for (int v : graph[u]) {
if (find(u) == find(v)) return false;
parent[find(v)] = find(graph[u][0]);
}
}
return true;
}
};func isBipartite(graph [][]int) bool {
n := len(graph)
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
for u := 0; u < n; u++ {
for _, v := range graph[u] {
if find(u) == find(v) {
return false
}
parent[find(v)] = find(graph[u][0])
}
}
return true
}var isBipartite = function(graph) {
const n = graph.length;
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let u = 0; u < n; u++) {
for (const v of graph[u]) {
if (find(u) === find(v)) return false;
parent[find(v)] = find(graph[u][0]);
}
}
return true;
};function isBipartite(graph: number[][]): boolean {
const n = graph.length;
const parent: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let u = 0; u < n; u++) {
for (const v of graph[u]) {
if (find(u) === find(v)) return false;
parent[find(v)] = find(graph[u][0]);
}
}
return true;
}