LeetCode 785. 判断二分图

原题目：https://leetcode-cn.com/problems/is-graph-bipartite/

 

思路：

先对所有的点做0标记，然后进行广度优先遍历

规则：与点m相连的所有点都应该染成与m不同的颜色，发生冲突（该点已被染色，且与m相同）就返回错误

 

代码：

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> g(n,0);

        //防止有独立的点
        for(int i=0;i<n;++i){
            if(g[i]==0){
                queue<int> q;
                q.push(i);
                g[i] = 1;

                while(!q.empty()){
                    int node = q.front();q.pop();
                    // 与他相连的点，应该做不同的标记
                    int c = (g[node]==1? 2:1);

                    for(int j:graph[node]){
                        if(g[j]==0){
                            g[j] = c;
                            q.push(j);
                        }
                        //发生冲突
                        else if(g[j] != c){
                            return false;
                        }
                    }
                }
            }
        }
        return true;

    }
};