HDU1611 The Suspects 【并查集】

题目链接：POJ-1611

kuangbin带你飞【专题五 并查集】

题目描述：

有n个同学，编号为0 - n-1 ， 每次给出一定的同学为一组， 问最后和0号在一个集合的有多少人

思路:

合并集合的时候，把集合的大小也进行合并，就可以求出集合的人数；

代码:

#include <iostream>
using namespace std;int pre[30010], size[30010];void init(int n)
{
    for(int i = 0; i<n; i++){
    pre[i] = i;size[i] = 1;}
}int Find(int x)
{
    return x == pre[x] ? x : pre[x] = Find(pre[x]);
}void Union(int x, int y)
{
    x = Find(x);y = Find(y);if(x != y){
    pre[x] = y;size[y] += size[x];}
}int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n , m;while(cin >> n >> m, n + m){
    init(n);for(int i = 1; i<=m; i++){
    int k;cin >> k;int key;for(int j = 1; j<=k; j++){
    int tmp;cin >> tmp;if(j == 1){
    key = tmp;continue;}else{
    Union(key, tmp);}}}cout<<size[Find(0)]<<endl;}return 0;
}