785. 判断二分图：DFS 染色与冲突检测

二分图的顶点可以分成两个集合，任意边只连接不同集合。把两个集合抽象为 0 与 1 两种颜色，就得到 DFS/BFS 染色问题。

1
class Solution {
2
public:
3

4
    vector<int> color;
5
    vector<vector<int>> graphs;
6

7
    bool isBipartite(vector<vector<int>>& graph) {
8
        int n = graph.size();
9
        graphs = graph;
10

11
        color.assign(n, -1);
12

13
        for(int i = 0; i < n; i ++ ) {
14
            if(color[i] == -1) {
15
                if(!dfs(i, 0)) return 0;
16
            }
17
        }
18

19
        return 1;
20
    }
21

22
    int dfs(int u, int c) {
23
        color[u] = c;
24

25
        for(auto& v : graphs[u]) {
26
            if(color[v] == -1) {
27
                if(!dfs(v, 1 - c)) return 0;
28
            }
29
            else if(color[v] == color[u]) {
30
                return 0;
31
            }
32
        }
33

34
        return 1;
35
    }
36
};

图可能不连通，不能只从 0 号节点开始。每个未染色节点都应作为一个新连通分量的起点。时间复杂度为 $O(V+E)$ ，空间复杂度为 $O(V)$ 。