poj 1611 The suspects

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

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

最后

以上就是愉快西牛为你收集整理的poj 1611 The suspects的全部内容，希望文章能够帮你解决poj 1611 The suspects所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。