POJ 1182 食物链[并查集]

此题利用并查集解决。

对于每只动物i创建3个元素i-A，i-B，i-C，并用这3*N个元素建立并查集。

1·i-x表示“i属于种类x”

2·并查集你的每一组表示组内所有元素代表的情况同时发生或不发生。

对于每一条信息，只需要按照下列操作即可：

1.第一种：x，y同类，合并x-A和y-A、x-B和y-B、x-C和y-C。

2.第二种：x吃y，，，合并x-A和y-B、x-B和y-C、x-C和y-A。

当然，在合并之前，需要判断合并是否会产生矛盾，若有矛盾，则结果+1；

代码：

#include 
  
   
#include 
   
     using namespace std; #define MAX_K 100000 int par[MAX_K],rank[MAX_K]; int t[MAX_K],x[MAX_K],y[MAX_K]; //以下是并查集的函数 void init(int n) { for(int i=0;i
    
     =n||y<0||y>=n) { ans++; continue; } if(t==1) //xy是同类 { if(same(x,y+n)||same(x,y+2*n)) { ans++; } else { unite(x,y); unite(x+n,y+n); unite(x+2*n,y+2*n); } } else //x吃y { if(same(x,y)||same(x,y+n*2)) { ans++; } else { unite(x,y+n); unite(x+n,y+2*n); unite(x+2*n,y); } } } printf(%d ,ans); return 0; }