1107 Social Clusters （30 分）（并查集）

并查集的基本应用

#include<bits/stdc++.h>

using namespace std;
const int N=1e3+10;
vector<int>vec[N];
int p[N];
const int inf=0x3f3f3f3f;
int isroot[N]={0};
int course[N]={0};
int findth(int x)
{
    if(x==p[x]) return x;
    return p[x]=findth(p[x]);
}

void unionn(int x,int y)
{
    int xx=findth(x);
    int yy=findth(y);
    if(xx!=yy){
        p[yy]=xx;
    }
}

bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<=N;i++) p[i]=i;
    for(int i=1;i<=n;i++){
        int k;
        char ch;
        scanf("%d%c",&k,&ch);
        for(int j=0;j<k;j++){
            int x;
            scanf("%d",&x);
            if(course[x]==0){
                course[x]=i;//这个相当于标记一下，如果x这个活动没有人选就把i赋值给他  如果有了 就把他和i放在一个并查集里
            }
            unionn(i,course[x]);
        }
    }
    for(int i=1;i<=n;i++){
        isroot[findth(i)]++;//这个是求有几个集合  每个集合里有几个常用的算法
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(isroot[i]!=0) ans++;
    }
    sort(isroot+1,isroot+n+1,cmp);
    printf("%d
",ans);
    for(int i=1;i<=ans;i++){
        if(i!=1) printf(" ");
        printf("%d",isroot[i]);
    }
    printf("
");

    return 0;
}