一道“扩展域”并查集的题目，我们把每一个点拆分成三个域：同类、食物、天敌。
我们假设x的同类域为x，食物域为x+n，天敌域为x+n+n。假设x与y是同类，那么说明x+n与y+n是同类，x+n+n与y+n+n是同类。
假设x吃y，那么x+n与y是同类，x+n+n与y+n是同类，x与y+n+n是同类。
现在我们只需要判断一句话与之前处理的关系是否冲突即可，如果不冲突，就按照上面的同类关系合并即可；冲突则统计答案。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int n,m; 6 int f[50010*3]; 7 int find(int x) { 8 if(f[x]!=x) f[x]=find(f[x]); 9 return f[x]; 10 } 11 void add(int x,int y) { 12 f[find(x)]=find(y); 13 } 14 int main() { 15 cin>>n>>m; 16 for(int i=1;i<=n*3;i++) f[i]=i; 17 int ans=0; 18 for(int i=1;i<=m;i++) { 19 int op,x,y; 20 cin>>op>>x>>y; 21 if(x>n||y>n) { 22 ans++; 23 continue ; 24 } 25 if(op==1) { 26 if(find(x)==find(y+n)||find(x)==find(y+n+n)) ans++; 27 else { 28 add(x,y); 29 add(x+n,y+n); 30 add(x+n+n,y+n+n); 31 } 32 } 33 else if(op==2) { 34 if(find(x)==find(y)||find(x)==find(y+n)) ans++; 35 else { 36 add(x,y+n+n); 37 add(x+n,y); 38 add(x+n+n,y+n); 39 } 40 } 41 } 42 cout<<ans<<endl; 43 return 0; 44 }
原文：https://www.cnblogs.com/shl-blog/p/10803795.html
