$$\color{Purple}{kuangbin题解目录}$$
描述
某学校共有 $n$ 个学生,编号 $0 \\sim n-1$。
该学校共有 $m$ 个社团。
每个学生可以加入多个社团,也可以不参加任何社团。
该学校所在的地区爆发了非典型肺炎。
经查实,$0$ 号学生为病毒携带的可疑人员,需要进行隔离观察。
为了防止疫情传播,学校还规定,一旦某社团出现病毒携带的可疑人员,则该社团的全体成员将全部被划分为病毒携带的可疑人员。
请你计算,该学校最终共有多少名学生被判定为病毒携带的可疑人员。
输入格式
输入包含多组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行描述一个社团的人员,首先包含一个整数 $k$,表示该社团的人数,然后包含 $k$ 个整数,表示每个社员的编号。
当输入 $n=0,m=0$ 时,表示输入结束。
输出格式
每组数据输出一行结果,表示被判定为病毒携带的可疑人员的学生数量。
数据范围
输入最多包含 $10$ 组数据。
$1 \\le n \\le 30000$,
$0 \\le m \\le 500$,
$1 \\le k \\le n$。
输入样例:
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
输出样例:
4
1
1
思路
- 考虑采用
并查集
解决,每一个团队以第一个成员作为当前团队的公共合并点
,其他成员与之合并
,最后计算与学生$0$构成在同一集合的成员个数
;- 此处的成员个数可维护
每个点中的集合个数
,可快速计算出对应的结果.
代码
// Problem: 可疑人员
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4270/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-23 21:09:18
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 30010
using namespace std;
typedef long long ll;
int n,m;
int res;
int fa[MAXN],siz[MAXN];
int find(int x)
{
if(fa[x]!=x)
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
res=0;
for(int i=0;i<=n-1;i++)
fa[i]=i,siz[i]=1;
for(int i=1;i<=m;i++)
{
int k,x,y;
scanf("%d %d",&k,&x);
for(int j=2;j<=k;j++)
{
scanf("%d",&y);
int fx=find(x),fy=find(y);
if(fx!=fy)
{
fa[fx]=fy;
siz[fy]+=siz[fx];
}
}
}
int root=find(0);
for(int i=0;i<=n-1;i++)
{
int fx=find(i);
if(fx==root)
res++;
}
printf("%d\n",res);
/*
printf("%d\n",siz[find(0)]);
*/
}
return 0;
}