PAT A1107 Social Clusters

题目链接

解题思路

使用并查集做这道题目，思路是将每个有相同爱好的人合并为一个集合，也就是有相同的根节点。再合并时注意合并的是每个人的编号从1~n，不是后面hobby的编号，可以使用一个数组来表示hobby，初始时让hobby指向前面的人的编号。如果hobby不为0，说明前面已经出现过，就将此时人的编号i合并到findFather(hobby[x])的编号上。最后设置一个数组，找出每一个人的根节点，一根节点维数组下标加一，即这一组的人数。

注意

找一个数的根节点最好用findFather，father虽然有的地方可以，但是不知道为啥isRoot[father[i]]++;//根节点加一就不行了，就必须用findFather。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1010;
int n,father[maxn],isRoot[maxn]={0},hobby[maxn]={0};
bool cmp(int a,int b) {return a>b;}
int findFather(int x){
    if(x==father[x]) return x;
    else {
        int F=findFather(father[x]);
        father[x]=F;
        return F;
    }
}

void Union(int a,int b){
    int faA=findFather(a);
    int faB=findFather(b);
    if (faA!=faB){
        father[faA]=faB;
    }
}

int main(){
    scanf("%d",&n);
    int m,x;
    for(int i=1;i<=n;i++) father[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d:",&m);
        for(int j=0;j<m;j++){
            scanf("%d",&x);
            if (hobby[x]==0) hobby[x]=i;//初始
            Union(i,findFather(hobby[x]));//注意是把人的编号合并到一个集合
        }
    }
    for(int i=1;i<=n;i++){
        isRoot[findFather(i)]++;//根节点加一
//        printf("fa:%d ",father[i]);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if (isRoot[i]!=0) cnt++;
    }
    sort(isRoot+1,isRoot+n+1,cmp);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++){
        printf("%d",isRoot[i]);
        if (i<cnt) printf(" ");
    }

    return 0;
}