题目链接

886. 可能的二分法

题意：

给定一组 N 人（编号为 1, 2, …, N）， 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

思路：

1. 法一：DFS+染色

   首先初始化所有节点的颜色为0，然后给没有染色的节点染上1，给这个节点的相邻节点染色上-1，以此类推，判断相邻的两个节点颜色相同即可

2. 法二：种类并查集

   如果a和b不能是相同颜色，那么我们可以合并(a,b+N),(b,a+N)为相同颜色，这样每次判断fa[a]和fa[b]相同即可

   class Solution {
   public:
   //方法二：种类并查集
   vector fa;
   int findroot(int x){
   if(fa[x]==x) return x;
   return fa[x]=findroot(fa[x]);
   }
   void merge(int a,int b){
   a=findroot(a);
   b=findroot(b);
   fa[a]=b;
   }
   bool possibleBipartition(int N, vector>& dislikes){
   fa=vector(N2+1,0);//开两倍空间(a,b+N),(b,a+N)来存 //初始化fa[]数组 for(int i=1;i<=2N;i++) fa[i]=i;

       for(vector<int> tmp:dislikes){
           int x=findroot(tmp[0]);
           int y=findroot(tmp[1]);
           if(x==y) return false;
           //合并(a,b+N)
           merge(tmp[0],tmp[1]+N);
           merge(tmp[1],tmp[0]+N);
       }
       return true;
   } 
   
   //方法一：
   //DFS + 染色
   // vector<int> col;//染色
   // vector<unordered_set<int>> ed;
   // bool dfs(int c,int k){
   //     col[k]=c;
   //     for(auto it=ed[k].begin();it!=ed[k].end();it++){
   //         if(col[*it]==col[k]) return false;
   //         if(!col[*it] && !dfs(-1*c,*it)) return false;
   //     }
   //     return true;
   // }
   // bool possibleBipartition(int N, vector<vector<int>>& dislikes){
   //     col=vector<int>(N+1,0);//N个节点的颜色
   //     ed=vector<unordered_set<int>>(N+1);
   
   //     for(vector<int> tmp:dislikes){
   //         ed[tmp[0]].insert(tmp[1]);
   //         ed[tmp[1]].insert(tmp[0]);//创立邻接链表
   //     }
   
   //     for(int i=1;i<=N;i++){
   //         if(!col[i] && !dfs(1,i)) return false;
   //     }
   
   //     return true;
   // }
   
   // static bool cmp(vector<int> a,vector<int> b){
   //     if(a[0]==b[0]) return a[1]<b[1];
   //     return a[0]<b[0];
   // }
   // bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
   //     vector<vector<int>> ans;
   //     for(vector<int> tmp:dislikes){
   //         if(tmp[0]>tmp[1]) swap(tmp[1],tmp[0]);
   //         ans.push_back(tmp);
   //     }
   
   //     sort(ans.begin(),ans.end());
   //     set<int> s1,s2;
   //     for(vector<int> tmp:ans){
   //         if(s1.count(tmp[1]) || s2.count(tmp[0])) return false;
   //         s1.insert(tmp[0]);
   //         s2.insert(tmp[1]);
   //     }
   //     return true;
   // }

   };