这道题自己写的在自己机子上通过了,但提交的时候还是错误,和别人的代码对照了一下,发现就是判断父节点的条件没写好.网上有不少关于并查集的介绍,随手百度一下就行.我自己没有详细介绍并查集是怎么实现的,并不是自己不想分享知识,而是自己的水平差的太远,还有csdn的博客上传图片非常坑,但自己确实在网上学习了不少的东西.对于acm新手来说,坚持和自学是必须的.
对于代码的理解最好自己手写运算一遍.
#include<iostream>
#include<cstdio>
using namespace std;
//厉害,在读取完k后,利用for来合并
#define MAX 30010
#define MAXN 550
int father[MAX],son[MAX];
int i,j;//循环变量
void Uset(int n)//初始化father[]和son[],如:father[2]=1;说明2的父节点是序号1.son[1]=3,是说序号1的共有3个节点,包括自身.
{
for(i=0;i<n;i++)
{
father[i]=i;
son[i]=1;
}
}
int find(int x)//寻找父节点
{
return (x == father[x] ? x :find(father[x]));
}
void Union(int x,int y)//合并运算
{
int root1=find(x);
int root2=find(y);
if(root1!=root2)//我自己错在这里了
{
father[root2]=root1;
son[root1]+=son[root2];
}
// else
// {
// father[root1]=root2;
// son[root2]+=son[root1];
// }
}
int main()
{
int n,m,k,a,b,c;//
freopen("1611.txt","r",stdin);
while(1)
{
scanf("%d%d",&n,&m);
if(n==0 && m==0)
break;
Uset(n);
while(m--)
{
cin>>k>>a;
for(i=1;i<k;i++)//怎样区分0?
{
scanf("%d",&b);
Union(a,b);
}
}
printf("%d\n",son[find(0)]);//真厉害,程序的美丽或许正在于此,记
//son永远在找下属集合
}
return 0;
}
原文：http://blog.csdn.net/yuzibo747/article/details/19501387