poj 1611 The suspects

96 阅读 0 评论 64 点赞

我是靠谱客的博主愉快西牛，这篇文章主要介绍poj 1611 The suspects，现在分享给大家，希望可以做个参考。

（1）类型：并查集
（2）题意：n个学生分属m个团体，一个学生可以属于多个团体。一个学生疑似患病，则它所属的整个团体都疑似患病。已知0号学生疑似患病，以及每个团体由那些学生构成，求一共多少个学生疑似患病。
（3）解题思路：最简单的并查集，将所有疑似患病的学生合并起来即可。
（4）时间复杂度：O（n）级别的复杂度。
（5）总结：并查集的模板题目。因为学习java，已经好久没有写博客和打代码了。惭愧惭愧。本来就是个菜鸟，还因为其他的在此生死边缘挣扎。加紧练习完java，回来搞acm吧。
（6）代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
const int MAX=3e4+7;
int n,m,k,par[MAX],total[MAX];
int GetPar(int a){
    return par[a]==a?a:par[a]=GetPar(par[a]);
} 
void Merge(int a,int b){
    int p1=GetPar(a),p2=GetPar(b);
    if(p1==p2)return ;
    total[p1]+=total[p2];
    par[p2]=p1;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>n>>m,n||m){
        for(int i=0;i<n;i++){
            par[i]=i;total[i]=1;
        }
        for(int i=0;i<m;i++){
            int h,s;cin>>k>>h;
            for(int j=1;j<k;j++){
                cin>>s;Merge(h,s); 
            }
        }
        cout<<total[GetPar(0)]<<endl;
    }
}