poj 1182 并查集

#include <stdio.h>
int father[50050];
void initializtion(int n)
{
	for(int i=0; i<=n+1; i++)
		father[i] = i;
}
bool find(int a, int b)
{
	//int flag = 0;
	if(a==b)	return 0;
	else
	{
		int temp = a;
		if(temp == a && father[temp] == b)
			return 0;
		while(father[temp] != temp)
		{
			temp = father[temp];
			if(temp == b)	return 1;
			if(temp == a)	return 1;
		}
		return 0;
	}
}
void update(int a, int b)
{
	int i = a;
	if(i == a && father[i] == b)
			return ;
	while(father[i] != i)
	{
		i = father[i];
		
	}
	father[i] = b;
}
int main()
{
	int N, K;
	while(scanf("%d%d", &N, &K)!=EOF)
	{
		initializtion(N);
		int mistake = 0;
		int a, b, c;
		for(int i=0; i<K; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			if(b>N || c>N)
			{mistake++;		continue;}
			if(a==1)
			{
				if(find(b, c) )		mistake ++;
			}
			if(a==2)
			{
				if(b==c)	mistake++;
				else
				{
					if(find(b, c) )	mistake++;
					else update(b, c);
				}
			}
		}
		printf("%d\n", mistake);
	}
	return 0;
}

附件列表