题意是爆发了SARS病毒,现在有许多个小组,只要小组里有一个人感染了病毒,那么这个小组都会有感染的嫌疑,所以让求的就是有感染嫌疑的人数,先输入n,m,表示有n个人,m个小组,然后输入每个小组ans个人,然后输入那ans个人的编号。所以我们可以先输入ans,再输入第一个人a,然后再循环输入ans-1次b,让a和b合并就好了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 30005;
int pre[MAXN];
int n,m,ans,a,b;
void init(){
for(int i=0;i<=n;i++){
pre[i] = i;
}
}
int Find(int x){
if(x != pre[x]){
pre[x] = Find(pre[x]);
}
return pre[x];
}
void merge(int x, int y){
int fx = Find(x);
int fy = Find(y);
if(fx != fy){
pre[fy] = fx;
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==0 && m==0) break;
init();
while(m--){
scanf("%d%d",&ans,&a); // 输入该小组有ans个人和第一个人的编号a
for(int i=0;i<ans-1;i++){
scanf("%d",&b); // 循环输入ans-1次b
merge(a,b); // 合并a和b
}
}
int sum = 0;
for(int i=0;i<n;i++){
if(Find(0) == Find(i)) sum++; // 如果和0编号有关系,就有嫌疑
}
printf("%d\n",sum);
}
return 0;
}