The Suspects （并查集）

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

---

题意

n个学生，分m组，一组中一人有嫌疑则全组都有嫌疑

规定学生0有嫌疑

找出多少人有嫌疑

---

思路

用并查集把同一个组的人连接起来

查找和f[0]相同的共有多少人即可

---

代码

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 30010
int f[N],a[N];
int n,m,k;
int getf(int v)
{if(f[v]==v) return v;return f[v]=getf(f[v]);
}
void merge(int x,int y)
{int t1=getf(x);int t2=getf(y);if(t1!=t2)f[t2]=t1;return;
}
int main()
{while(~scanf("%d%d",&n,&m)&&(n+m)){for(int i=0;i<n;i++)f[i]=i;for(int i=1;i<=m;i++){scanf("%d",&k);scanf("%d",&a[1]);for(int j=2;j<=k;j++){   scanf("%d",&a[j]);merge(a[j-1],a[j]);  //每人与其前一个人连接起来}}for(int i=0;i<n;i++)f[i]=getf(f[i]);    //更新所有人信息int ans=0;for(int i=0;i<n;i++)if(f[i]==f[0]) ans++;printf("%d\n",ans);}return 0;
}

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

---