Leetcode: 785. Is Graph Bipartite?

这题目最一开始要做的事情就是，搞清楚什麽是bipartite？

一张图具有bipartite的性质的话，代表可以分成bi个party，然後里面的元素都可以跟对面party连紧紧(随意胡诌)。

可以把图里的node分成两个独立集合，独立集合也就是说两个交集没结果，然後可以全连接这样。
　
　
　

思路：

我只能感受到...边要偶数条边，还有图里面，一定会有复数个点，他们连到的点是相同的。

但还是没想法。

吸收知识时间

这题可以把她等价转换成涂色问题，bipartite还有一个性质，而且是解问题的关键：连线只在不同集合之间，同个集合的点是不会有连线的，所以可以在BFS中，把该点连接出去的邻居都涂上不同颜色，只要没有冲突，就继续涂色，直到把所有点分成不同颜色为止。
　
　
　

程序码

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n); // [0, 1, -1] = [uncolor, A, B] = [unvisited, 已分组, 已分组]
        
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (color[i]) continue;
            
            color[i] = 1;
            q.push(i);
            while(!q.empty()) {
                int curr_node = q.front();
                for (int neighbor: graph[curr_node]) {
                    if (!color[neighbor]) {
                        color[neighbor] = -color[curr_node];
                        q.push(neighbor);
                    }
                    else if (color[neighbor] == color[curr_node])
                        return false;
                }
                q.pop();
            }
        }
        return true;
  }
};

大神

for (q.push(i); !q.empty(); q.pop()) { 
    ... 
}

我从来..没试过把queue跟for结合，好厉害！

参考：
https://leetcode.com/problems/is-graph-bipartite/discuss/409594/Clean-C%2B%2B-BFS-with-explanation-and-comments
https://www.youtube.com/watch?v=oDqjPvD54Ss