LeetCode 886. 可能的二分法（着色DFS/BFS/拓展并查集）

示例 1：
输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：
输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：
输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false
 
提示：
1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j 

class Solution {
	unordered_map<int,unordered_set<int>> m;
	bool ans = true;
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
    	if(dislikes.size() <= 2) return true;
    	vector<int> color(N+1, 0);
    	for(auto& d : dislikes)//建图
    	{
    		m[d[0]].insert(d[1]);
    		m[d[1]].insert(d[0]);
    	}
    	for(int i = 1; i <= N; i++)
    	{
    		if(color[i] == 0)//未着色的
    		{
    			color[i] = 1;//着色为1
    			dfs(i, 1, color);
    			if(!ans)
    				return false;
    		}
    	}
    	return true;
    }
    void dfs(int id, int col, vector<int> &color)
    {
    	if(!ans) return;
    	int nextcol = col==1 ? 2 : 1;//跟我相连的(不喜欢的人)颜色相反
    	for(auto it = m[id].begin(); it != m[id].end(); it++)
    	{
    		if(color[*it] == col)//颜色相同，出错
    			ans = false;
    		if(color[*it] == 0)//没有访问过的，继续着色
	    	{
	    		color[*it] = nextcol;
	    		dfs(*it, nextcol, color);
	    	}
    	}
    }
};

class Solution {
	unordered_map<int,unordered_set<int>> m;
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
    	if(dislikes.size() <= 2) return true;
    	vector<int> color(N+1, 0);
    	for(auto& d : dislikes)//建图
    	{
    		m[d[0]].insert(d[1]);
    		m[d[1]].insert(d[0]);
    	}
        queue<int> q;
        int id, col = 1, nextcol, size;
    	for(int i = 1; i <= N; i++)
    	{
    		if(color[i] == 0)//未访问的
    		{
    			color[i] = 1;//着色为1
                col = 1;
    			q.push(i);
                while(!q.empty())
                {
                    size = q.size();
                    nextcol = col==1 ? 2 : 1;//下一层颜色需要变
                    while(size--)
                    {
                        id = q.front();
                        q.pop();
                        for(auto it = m[id].begin(); it != m[id].end(); it++)
                        {	//相连的，不喜欢的，颜色不能一样
                            if(color[*it] == col)
                                return false;
                            if(color[*it] == 0)
                            {
                                color[*it] = nextcol;//没访问的，不喜欢的，颜色跟我不一样
                                q.push(*it);
                            }
                        }
                    }
                    col = col==1? 2 : 1;//换颜色
                }
    		}
    	}
    	return true;
    }
};

class dsu
{
	vector<int> f;
public:
	dsu(int n)
	{
		f.resize(n+1);
		for(int i = 0; i < n+1; ++i)
			f[i] = i;
	}
	void merge(int a, int b)
	{
		int fa = find(a), fb = find(b);
		f[fa] = fb;
	}
	int find(int a)//循环+路径压缩
	{
        int origin = a;
		while(a != f[a])
			a = f[a];
		return f[origin] = a;//路径压缩
	}
};
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
    	if(dislikes.size() <= 2) return true;
    	dsu u(2*N+1);
        int a, b, da, db;
        for(auto& d : dislikes)
    	{
    		a = d[0];
            b = d[1];
            da = a+N;//a的另外一种颜色
            db = b+N;//b的另外一种颜色
            if(u.find(a) == u.find(b))
                return false;
            u.merge(a,db);//a跟b互斥，那么a跟b的反是一样的颜色
            u.merge(b,da);//同理
    	}
        return true;
    }
};