学步园

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

题目大意： 给你一群人，在这群人中编号为0的人得了传染病，这种病会传染给跟患者在同间病房的其他病人。然后告诉你有哪些房间及房间中有哪些人，问你最终得病的人有多少。

算法分析：在原有的并查集上加个人数统计就好了。

程序代码：

#include<cstdio>
#include<cstring>

#define MM 35000

int temp[MM],num[MM];

int find(int t)
{
	while(temp[t] != t)
		t = temp[t];
	return t;
}

void merge(int x, int y)
{
	int p = find(x), q = find(y);
	if(q != p){
		temp[q] = p,num[p] += num[q];//父节点所在组里人数要加上子节点所在组的人数。
	}
}

int sum()					//统计总共得病的人数
{
	int fath = temp[0];
	while(fath != temp[fath])
		fath = temp[fath];
	return num[fath];
}
inline void init(int n)
{
	for(int i = 0; i < n; i++)
		temp[i] = i,num[i] = 1;//初始时每个人所对应的组就只有自己，所以人数为1
}

int main()
{
	int n,m;
	while( scanf("%d%d", &n,&m) && (n || m) )
	{
		init(n);
		int num,per1,per2;
		while( m-- ){
			scanf("%d", &num);//拿每个组的第一个人和组里其他人进行查找合并
			scanf("%d",&per1);
			num--;				//因为第一个人先拿出来了，所以查找合并时要少一个人
			while( num-- ){
				scanf("%d", &per2);
				merge(per1,per2);
			}
		}
		printf("%d\n", sum());
	}
}