C - 食物链 POJ - 1182

C - 食物链 POJ - 1182，设虚点，若ab相同就连接ab，吃就连接a,b+n，a+n，b+2n, a+2n,b,设2组虚点方便理解ABC。

#include
#include
#define maxn 1000001

int n,k,ans=0;
int f[maxn*3],rank[maxn],d[maxn];

void prework()
{
	scanf("%d",&n);
	for(int i=1;i<=3*n+1;i++)
		f[i]=i;
	scanf("%d",&k);
}

int find(int x)
{
	if(f[x]==x)
		return x;
	else
		return f[x]=find(f[x]);
}

void unite(int x,int y){
	if(x==y)
		return;
	if(rank[x]>rank[y])
		f[y]=x;
	else{
		f[x]=y;
		if(rank[x]==rank[y])
			rank[y]++;
	}
}

void mainwork()
{
	int a,b,d,x,y,xx,yy;
	scanf("%d%d%d",&d,&a,&b);
	if(a<0 || b<0 || a>n || b>n )
	{
		ans++;
		return;
	}
	x=find(a+n);y=find(b+n);
	xx=find(a+2*n);yy=find(b+2*n);
	a=find(a),b=find(b);
	if(d==1)
	{
		if(a==y || a==yy || b==x || b==xx || yy==a 
		|| x==yy || y==xx)
		{
			ans++;
			return;
		}
		unite(a,b);unite(x,y);unite(xx,yy);
	}
	if(d==2)
	{
		if(a==b || x==y || xx==yy
		|| a==yy || x==b || xx==y)
		{
			ans++;
			return;
		}
		unite(a,y);unite(x,yy);unite(xx,b);
	}
	
}

void print()
{
	printf("%d",ans);
}

int main()
{
	prework();
	for(int i=1;i<=k;i++)
		mainwork();
	print();
	return 0;
}