首页 > 代码库 > poj1611
poj1611
0号患了病毒,只要和0号一组的人同样会患病毒。。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int bin[30010];
int q[30010];
int n,m;
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int findx(int x)
{
int r,j,k;
r=x;
while(bin[r]!=r)
r=bin[r];
k=x;
while(k!=r)
{
j=bin[k];
bin[k]=r;
k=j;
}
return r;
}
void merge(int x,int y)
{
int fx,fy;
fx=findx(x);
fy=findx(y);
if(fx!=fy)
{
bin[fx]=fy;
}
}
int main()
{
int n,x,t,i,j;
while(scanf("%d%d",&n,&x)!=EOF)
{
if(n==0&&x==0) break;
for(i=0;i<n;i++)
bin[i]=i;
while(x--)
{
scanf("%d",&t);
memset(q,0,sizeof(q));
for(j=0;j<t;j++)
scanf("%d",&q[j]);
qsort(q,t,sizeof(q[0]),cmp);
for(j=1;j<t;j++)
{
merge(q[j],q[j-1]);
}
}
/*for(i=0;i<n;i++)
printf("...%d",bin[i]);*/
int l=1;
for(i=1;i<n;i++)
{
if(findx(i)==findx(0))
l++;
}
printf("%d\n",l);
}
return 0;
}