求0号结点所在集合的元素个数
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <queue>
# define LL long long
using namespace std ; const int MAXN = ;
int F[MAXN];
int num[MAXN] ; int find(int x)//找x的祖先结点
{
if(F[x]==x) return x;
return F[x]=find(F[x]);
}
void bing(int u,int v) //按秩合并
{
int x = find(u);
int y = find(v);
if(x == y)
return ;
if(num[x] >= num[y])
{
F[y] = x;
num[x] += num[y];
}
else
{
F[x] = y;
num[y] += num[x];
}
}
int main()
{
// freopen("in.txt","r",stdin) ;
int n , m , k ;
while(scanf("%d %d", &n , &m) != EOF)
{
if (n == && m == )
break ; int i ;
for(i = ; i < n ; i++)
{
F[i] = i ;
num[i] = ;
}
int u , v ;
while(m--)
{
scanf("%d %d" , &k , &u) ;
k-- ;
while(k--)
{
scanf("%d" , &v) ;
bing(u , v) ;
}
}
printf("%d\n" , num[find()]) ; //集合元素的个数保存在祖先结点的num数组里 }
return ;
}