并查集简单题-pku1611
代码：
[cpp]
#include<stdio.h>
int father[30001];
int count[30001];
int i,m,n,first,a,b;
void setfather(int n) //初始化，将各自fahter设置为本身
{
for(i=0;i<n;i++)
{
father[i]=i;
count[i]=1;
}
}
int findfather(int i)
{
if(i!=father[i])
father[i]=findfather(father[i]);
return father[i];
}
void Untion(int a,int b)
{
int m1=findfather(a);
int m2=findfather(b);
if(m1==m2)
return;
if(count[m1]>=count[m2]) //若不相等，则将值赋值给较大的
{
father[m2]=m1;
count[m1]=count[m2]+count[m1];
}
else
{
father[m1]=m2;
count[m2]=count[m1]+count[m2];
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF&&n>0)
{
if(n>=0&&n<=30000&&m>=0&&m<=500)
{
setfather(n);
while(m>0)
{
scanf("%d %d",&a,&first);
for(i=0;i<a-1;i++)
{
scanf("%d",&b);
Untion(first,b);
}
m--;
}
printf("%d\n",count[findfather(0)]);
}
}
return 0;
}
#include<stdio.h>
int father[30001];
int count[30001];
int i,m,n,first,a,b;
void setfather(int n) //初始化，将各自fahter设置为本身
{
for(i=0;i<n;i++)
{
father[i]=i;
count[i]=1;
}
}
int findfather(int i)
{
if(i!=father[i])
father[i]=findfather(father[i]);
return father[i];
}
void Untion(int a,int b)
{
int m1=findfather(a);
int m2=findfather(b);
if(m1==m2)
return;
if(count[m1]>=count[m2]) //若不相等，则将值赋值给较大的
{
father[m2]=m1;
count[m1]=count[m2]+count[m1];
}
else
{
father[m1]=m2;
count[m2]=count[m1]+count[m2];
}
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF&&n>0)
{
if(n>=0&&n<=30000&&m>=0&&m<=500)
{
setfather(n);
while(m>0)
{
scanf("%d %d",&a,&first);
for(i=0;i<a-1;i++)
{
scanf("%d",&b);
Untion(first,b);
}
m--;
}
printf("%d\n",count[findfather(0)]);
}
}
return 0;
}
补充：软件开发 , C++ ,
