题意:将n个人分组,找出受感染的人有多少,当一个人感染,他所在的那一组均视为受感染。

分析:运用并查集将相关联的人都分到一个集合,然后判断每个人是否和0在同一个集合,若在则视为受感染,否则不是

#include<stdio.h>
const int MN=30010;
 
int father[MN],rank[MN],a[MN];
 
void init(int n)
{
for (int i=0;i<n;i++)
    {
father[i]=i;
rank[i]=1;//这个竟然忘记了,导致wa了3,4次
}
}
 
int Find(int x)
{
int r=x;
while(r!=father[r])
{
r=father[r];
}
if(r!=x)
father[x]=r;
return r;
}
 
void Union(int x,int y)
{
if(x==y) return ;
if(rank[x]>rank[y]) rank[y]=x;
else
{
if(rank[x]==rank[y]) rank[x]++;
else rank[y]++;
father[x]=y;
}
}
 
int main()
{
int n,m,i,k,j,ans;
while(1)
{
scanf("%d%d",&n,&m);
if(n==0 && m==0) break;
init(n);
ans=1;//记录人数
for (i=0;i<m;i++)
{
scanf("%d",&k);
for (j=0;j<k;j++)
{
scanf("%d",&a[j]);
}
if(k==1) continue;
for (j=1;j<k;j++)//并集合
{
int x=Find(a[j-1]);
int y=Find(a[j]);
Union(x,y);
}
}
father[0]=Find(father[0]);
for (j=1;j<n;j++)//找出和0同在一集合的人数
{
father[j]=Find(father[j]);
if(father[0]==father[j]) ans++;
}
// int t1,t2;
// for (t1=0;t1<3;t1++)
// {
// printf("%d ",father[i]);
// }
printf("%d\n",ans);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation