The Suspects(并查集)

发布于 2020-09-05  0 次阅读


题目大意:

The Suspects
给你学生数量n,以及m个学生团体
每个团体给你x个人和他们的编号,求与编号0在一个团体过的人数

思路:

很明显的并查集维护与0在一起过的人即可,同时记录一下每个祖先结点的值(即该集合的值)

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=3e4 +9;
int n, m, x, a, t;
int fa[N], ran[N];

int find(int u){
    if(fa[u]==u)    return u;
    return fa[u]=find(fa[u]);
}

void link(int a, int b){
    int aa=find(a), bb=find(b);
    if(aa!=bb){
        fa[bb]=aa;
        ran[aa]+=ran[bb];
    }
    return ;
}

void solve(){
    while(cin>>n>>m){
        if(n==0 && m==0)   return ;
        for(int i=0; i<=n; i++) fa[i]=i, ran[i]=1;
        for(int i=1; i<=m; i++){
            cin>>x;
            cin>>a;
            for(int j=1; j<=x-1; j++){
                cin>>t;
                link(a,t);
            }   
        }
        cout<<ran[find(0)]<<endl;
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生