说下题目大意。一共有n个学生(编号0 至 n-1),m个组,一个学生可以同时加入不同的组。现在有一种传染病,如果一个学生被感染,那么和他同组的学生都会被感染。现在已知0号学生被感染,问一共有多少个人被感染。
简单的并查集 直接看代码吧。
#include<stdio.h>
#include<string.h>
int f[200000],r[200000];
int find(int x) /* 找爸爸*/
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
int main()
{
 int i,a,b,m,n,s,x,y;;
 while(1)
 {
  scanf("%d %d",&m,&n);
  if(m==0&&n==0)
   break;
  if(n==0)
  {
   printf("1\n");
   continue;
  }                      /*判断,不能漏*/
  for(i=0;i<m+10;i++)
  {
   f[i]=i;
   r[i]=1;
  }                    /*赋初值*/
  while(n–)
  {
   scanf("%d",&s);
   if(s>0)
    scanf("%d",&a);
   for(i=1;i<s;i++)
   {
    scanf("%d",&b);
    x=find(a);
    y=find(b);
    if(x!=y)
    {
     if(r[x]>=r[y])
     {
      f[y]=x;
      r[x]+=r[y];
     }
     else
     {
      f[x]=y;
      r[y]+=r[x];
     }
    }            /*大部分人喜欢写个函数,这题比较少直接写主函数里面了(合并集合)*/
   } 
  }
  x=f[0];
  printf("%d\n",r[x]);
 }
  return 0;
}

发表评论

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

Post Navigation