POJ 1611
题意
有n个人参加了m个社团，同一个社团互相接触的人有感染非典的概率，已知0号同学是疑似病例，求总的疑似病例的人数。
思路
求并查集。
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 300001;
int pre[MAXN];
int n,m;
int find(int i){
int j = i,temp;
while(pre[i] != i)
i = pre[i];
while(j != i){
temp = pre[i];
pre[j] = i;
j = temp;
}
return i;
}
void merge(int b,int c){
int t1 = find(b);
int t2 = find(c);
if (t2 != t1){
pre[t2] = t1;
}
return;
}
int main(){
int i,j,k,c,d,sum;
while((scanf("%d%d",&n,&m)==2)&&(n||m)){
for(i = 0; i<n;i++){
pre[i] = i;
}
for (int i = 1; i <= m; ++i)
{
scanf("%d%d",&k,&d);
for(j = 1;j<k;j++){
scanf("%d",&c);
merge(c,d);
}
}
c = find(0);
sum = 1;
for(i=1;i<n;i++){
if(find(i) == c)
sum++;
}
printf("%d\n",&sum);
}
return 0;
}
