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;
}