网站seo规范临沂网站建设方案服务

题目链接：http://poj.org/problem?id=1611

 

题意：有学生感染了SARS。一个学生可以加入很多小组。n个学生m个小组，每个小组有k个组内成员，后跟着k个成员的组内编号。让你求出有多少学生受到了感染。

 

题解：并查集板子题。就是计数那里要注意。

 

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 30010;

int f[maxn];

void init(int n){
    for(int i = 0; i < n ;i++){
        f[i] = i;
    }
}

int find(int x){
    if(x == f[x])
        return x;
    return f[x] = find(f[x]); 
} 

void join(int a,int b){
    a = find(a);
    b = find(b);
    if(a != b){
        f[a] = b;
    }
}

int a[maxn];
int main(){
    int n,m,k;
    while(cin>>n>>m){
        if(n == 0 && m == 0){
            break;
        }
        init(n);
        for(int i = 0; i < m; i++){
            cin>>k;
            cin>>a[0];
            for(int j = 1; j < k ;j++){
                cin>>a[j];
                join(a[0],a[j]);
            }
        }
        int cnt = 0;
        for(int i = 0 ;i < n; i++){
            if(find(i) == f[0])        //point 
                cnt++;
        }
        cout<<cnt<<endl;
    }
    
    return 0;
}