poj_1161 并查集

题目大意

    一个学校里面有n个学生（标号从0到n-1）和m个社团（标号从0到m-1），每个学生属于0个或多个社团。近期有SARS传播，属于同一个社团的学生的SARS可以相互传染。给出m个社团中的学生标号，已知学生0被传染了SARS，求所有可能被传染SARS的人数。

题目分析

    典型的集合操作，求集合的大小。可以使用并查集来实现。学生0属于的所有社团中的所有学生都可能被传染，而这些所有和学生0属于相同社团的学生属于的所有社团的所有学生都可能被传染，如此递推下去，可以知道所有可能被传染的学生总数。（注意这里的“集合”并不是指“社团”）。 
    若学生s被传染，则将s加入到被传染的集合，同时将s属于的所有社团m中的所有学生加入到被传染的集合。假设这些学生本来有自己属于的集合k，这个操作相当于，将这些学生所属的所有集合进行合并。即需要将同一个社团的所有人的集合进行合并。 
    于是，可以在开始的时候设置每个学生单独属于自己的集合（即i = par[i])，在每次输入一个社团的时候，将该社团内的成员的集合进行合并。同时，需要维护每个集合内的成员数量的信息，这样在合并的时候需要更新。最后，求出学生0所属的集合的成员数量即可。

实现(c++)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX_STUDENT_NUM 30001
int gPar[MAX_STUDENT_NUM];			//每个学生属于的集合id
int gGroupNum[MAX_STUDENT_NUM];		//集合中的成员数量

//得到树的根
int GetPar(int c){
	if (c != gPar[c]){
		gPar[c] = GetPar(gPar[c]);
	}
	return gPar[c];
}

//将两个成员所在的集合进行合并
void Union(int a, int b){
	int p1 = GetPar(a);
	int p2 = GetPar(b);
	if (p1 != p2){
		gPar[p1] = p2;
		gGroupNum[p2] += gGroupNum[p1];
	}
}

//初始化集合
void InitGroup(int n){
	for (int i = 0; i < n; i++){
		gPar[i] = i;
		gGroupNum[i] = 1;
	}
}

int main(){
	int n, m, k, member, member0;
	while (true){
		scanf("%d %d", &n, &m);
		if (n == 0)
			break;
		InitGroup(n);
		for (int i = 0; i < m; i++){
			scanf("%d %d", &k, &member0);
			for (int j = 1; j < k; j++){
				scanf("%d", &member);
				Union(member, member0);
			}
		}
		int p = GetPar(0);
		printf("%d
", gGroupNum[p]);
	}
	return 0;
}