Leetcode 886. Possible Bipartition

 这一类的题目可以用union find也可以用普通的dfs，bfs来做。这里就用比较简单的着色法加bfs。思路就是给出发节点着蓝色，然后给该节点的子节点都着红色，子节点的子节点着蓝色，以此往复。如果在这个过程中发现矛盾，例如本该给一个节点着红色却发现它已经被着蓝色，说明必然有两个相邻节点要着同一种颜色。需要注意的是题目给的图不一定是联通的，因此可能需要遍历多次，以免遗漏。

时间复杂度：O(V+E)， 其中V是节点数，E 是连接数

空间复杂度: O(V+E)， 队列的大小是O(V), 邻接表的大小是O(E)

class Solution {

public:

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {

        if(n<=1) return true;

        vector<vector<int>> adjs(n+1);

        vector<int> color(n+1);

        for(auto dislike: dislikes){

            adjs[dislike[0]].push_back(dislike[1]);

            adjs[dislike[1]].push_back(dislike[0]);

        }

        for(auto dislike: dislikes){

            if(color[dislike[0]]==0){

                if(!bfs(dislike[0], adjs, color)){

                    return false;

                }

            }

        }

        return true;

    }

    bool bfs(int start, vector<vector<int>> adjs, vector<int>& color) {

        queue<int> q;

        q.push(start);

        color[start]=1;

        while(q.size()>0){

            for(int i=q.size()-1; i>=0; i--){

                int cur = q.front();

                q.pop();

                for(int next: adjs[cur]){

                    if(color[cur]==color[next]){

                        return false;

                    }else if(color[next]==0){

                        color[next]=-color[cur];

                        q.push(next);

                    }

                }

            }

        }

        return true;

    }

};