poj 1703 Find them, Catch them(关系并查集)

http://poj.org/problem?id=1703

题意：

有两个帮派，有两种操作 D a b表示a 和 b不是一个帮派；A  a b 表示询问a b是否是一个帮派，若至此还不确定，输出“Not sure yet”。

思路：关系并查集。只要两者的关系确定了，就将他们放入同一个集合内，而另外增加一个表示关系的数组r[ ]来表示该节点与其父亲的关系。0表示同一类，1表示不同类。初始时集合只有自己一个元素，r[ ]设置为0。

#include <stdio.h>
#include <string.h>
const int maxn = 100005;

int n,m;
int p[maxn];//保存父节点
int r[maxn];//保存与父节点的关系，0为同类。1为不同类

void make_set()
{
	for(int i = 1; i <= n; i++)
	{
		p[i] = i;
		r[i] = 0;
	}
}

int find(int x)
{
	if(x == p[x])
		return x;
	int tmp = p[x];//记录父亲节点，方便更新r[].
	p[x] = find(p[x]);
	r[x] = (r[x]+r[tmp])%2;//根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系  
	return p[x];
}

void merge(int a, int b)
{
	int fa = find(a);
	int fb = find(b);
	p[fa] = fb;
	r[fa] = (r[a]+r[b]+1)%2;//fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系 
}

int main()
{
	int test,a,b;
	char str[2];
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&n,&m);
		make_set();
		while(m--)
		{
			scanf("%s %d %d",str,&a,&b);

			if(str[0] == ‘A‘)
			{
				if(find(a) != find(b))//如果根节点不同，则不能判断关系  
				{
					printf("Not sure yet.\n");
					continue;
				}
				else
				{
					if(r[a] == r[b])
						printf("In the same gang.\n");
					else printf("In different gangs.\n");
				}
			}
			else
			{
				merge(a,b);
			}
		}
	}
	return 0;
}

poj 1703 Find them, Catch them(关系并查集)

原文：http://blog.csdn.net/u013081425/article/details/19408095