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;
}