POJ - 1611 The Suspects并查集模版

本文主要是介绍POJ - 1611 The Suspects并查集模版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-1611

题意

给定n学生，m小组，0号学生是病人，一组中只要有一个病人全部得病，求病人人数

思路

并查集模版，把每个组的学生分别连在一起，最后遍历全部节点即可。

代码

#include<iostream>  
#include<cmath>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;const int maxn=30500;const int inf=0x3f3f3f3f;int fa[maxn*3];int ra[maxn];int n,m,k;void init(){for(int i=0;i<maxn;i++){fa[i]=i;ra[i]=0; }return ;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void unite(int x,int y){x=find(x); y=find(y);if(x==y)return ;else if(ra[x]<ra[y]){fa[x]=y;} else{fa[y]=x;if(ra[x]==ra[y])ra[x]++;}}int main(){IOSwhile(cin>>n>>m){if(n==0&&m==0)break;init();while(m--){cin>>k;int a,b;cin>>a; k--;while(k--){cin>>b;unite(a,b);}}int fa=find(0);int ans=1;for(int i=1;i<n;i++)if(fa==find(i))ans++;cout<<ans<<endl;}}

这篇关于POJ - 1611 The Suspects并查集模版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---