785. Is Graph Bipartite?

發表於 | 分類於

problem

solution

option 1 - dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:
    bool ok = true;
    vector<bool> color, visited;
    void traverse(vector<vector<int>> graph, int v){
        // 已經確定不是二分圖了
        if(!ok) return;
        visited[v] = true;
        for(int w:graph[v]){
            // 拜訪鄰居 w
            if(!visited[w]){
                color[w] = !color[v];
                traverse(graph, w);
            }
            else{
                // 鄰居w 已經被拜訪過了
                if(color[w] == color[v]){
                    ok = false;
                }
            }
        }
    }
public:
    
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        color = vector<bool>(n, false);
        visited = vector<bool>(n, false);
        for(int v=0;v<n;++v){
            if(!visited[v]){
                traverse(graph, v);
            }
        }
        return ok;
    }
};

option 2 - bfs