本文出自：http://blog.csdn.net/svitter
题意：0号学生染病，有n个学生，m个小组。和0号学生同组的学生染病，病能够传染。
输入格式：n,m
数量 学生编号1，2,3,4
//m个分组
题解：最为典型的并查集。
解法一：求出全部的集合，然后求出0的parent，把parent为0的parent全部学生求出。
解法二：在计算的过程中统计total；
解法一：(一開始用的Vim写的在POJ上交出现 訪问禁止错误- - 不知道又奇妙的碰上了什么BUG，删了main函数中几个换行符就好了）
#include <iostream>
#include <stdio.h>
using namespace std; int stu[30001];
//the num of stu, group
int n, m; void init()
{
for(int i = 0; i < n; i++)
stu[i] = i;
} int getParent(int a)
{
if(a == stu[a])
return a;
else
return stu[a] = getParent(stu[a]);
} void Merge(int a, int b)
{
if(getParent(a) == getParent(b))
return; else
stu[getParent(a)] = b;
} int main()
{
int i, j;
int deter, sum;
int num;
int temp1, temp2; while(scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0)
break;
init();
for(i = 0; i < m; i++)
{
scanf("%d", &num);
scanf("%d", &temp1);
for(j = 1; j < num; j++)
{
scanf("%d", &temp2);
Merge(temp1, temp2);
}
}
deter = stu[getParent(0)];
sum = 1;
for(i = 1; i < n; i++)
{
if(getParent(i) == deter)
sum++;
} printf("%d\n", sum);
}
return 0;
}
解法二：
#include <iostream>
#include <stdio.h>
using namespace std; int stu[30001];
int total[30001];
//the num of stu, group
int n, m; void init()
{
for(int i = 0; i < n; i++)
{
stu[i] = i;
total[i] = 1;
}
} int getParent(int a)
{
if(a == stu[a])
return a;
else
return stu[a] = getParent(stu[a]);
} void merge(int a, int b)
{
if(getParent(a) == getParent(b))
return; else
{
total[getParent(a)] += total[getParent(b)];
stu[getParent(b)] = a;
}
} int main()
{
int i, j;
int num;//record the group's num
int temp1, temp2; while(scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0)
break;
init();
for(i = 0; i < m; i++)
{
scanf("%d", &num);
scanf("%d", &temp1);
for(j = 1; j < num; j++)
{
scanf("%d", &temp2);
merge(temp1, temp2);
}
} printf("%d\n", total[getParent(0)]); //不能直接stu[0],由于stu[0]不一定是根节点。
}
return 0;
}