POJ1182 食物链 【并查集变种】

挺简单的

N个元素扩展为 3*N个

i-A i-B i-C

A吃B吃C吃A

挑战程序设计的89面

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

int N,K;

const int MAX_N=333333;

//并查集

int par[MAX_N];

int rank[MAX_N];//树的高度

void init(int n)

{

	for(int i=0;i<n;i++)

	{

		par[i]=i;

		rank[i]=0;

	}

}

int find(int x)//

{

		if(par[x]==x)

			return x;

		else

			return par[x]=find(par[x]);

}

//合并x和y所属的集合

void unite(int x,int y)

{

	x=find(x);

	y=find(y);

	if(x==y)

		return;

	if(rank[x]<rank[y])

		par[x]=y;

	else

	{

		par[y]=x;

		if(rank[x]==rank[y])

			rank[x]++;

	}

}

//推断x和y是否同属于一个集合

bool same(int x, int y)

{

	return find(x)==find(y);

}

int main()

{

	#ifndef ONLINE_JUDGE

		freopen("G:/1.txt","r",stdin);

		freopen("G:/2.txt","w",stdout);

	#endif

    scanf("%d%d",&N,&K);

	init(3*N);

	int kind,a,b;

	int ans=0;

	for(int i=0;i<K;i++)

	{

		scanf("%d%d%d",&kind,&a,&b);

		int x=a-1;

		int y=b-1;

		if(x<0||x>=N||y<0||y>=N)

		{

			ans++;

			continue;

		}

		if(kind==1)

		{

			if(same(x,y+N)||same(x,y+2*N))

			{

				ans++;

				continue;

			}

			unite(x,y);

			unite(x+N,y+N);

			unite(x+2*N,y+2*N);

		}

		else

		{

			if(same(x,y)||same(x+N,y+N)||same(x+2*N,y+2*N)||same(x,y+2*N))

			{

				ans++;

				continue;

			}

			unite(x,y+N);

			unite(x+N,y+2*N);

			unite(x+2*N,y);

		}

	}

	printf("%d\n",ans);

	return 0;

}