PAT A1107 Social Clusters (30分)

并查集的优势在于合并与查询快速（路径压缩后）
在union操作中，如果不按照根结点合并的原则很容易漏点造成合并的集合只有部分进行合并而剩下一部分并当作另一个部分。
比如我一开始处理有相同爱好的人群，使用了：
for(int j = 0; j < hobby[i].size()-1;j++){//从1到n-1
father[hobby[i][j+1]] = father[hobby[i][j]];
}
这一过程如果father[hobby[i][j+1]]之前与自己其他爱好的爱好者组成集合，容易造成该集合的断裂，尤其是hobby[i][j+1]是低序列者
所以解决方案有：
1.在赋值之前判断是否曾经被赋值过，如果赋值过则合并两个根节点进行结合
2.无论是否赋值过都直接进行union操作，将前面的全部可能有的集合包含到正在处理的集合中
我采用了第二种方案

#include<cstdio>
#include<vector>
#include<set>
#include <algorithm>
using namespace std;
const int N=1010;//最大人数
const int H = 1010;//最大爱好数
int father[N];//并查集 ，1...N-1
vector<int> hobby[H];//爱好集 ，1...H-1
int n;//总人数
set<int> cluter;//存储集合
int cluter_count[N];//记录每个集合的个数

void init(int n){
    for(int i = 1;i<=n;i++){
        father[i]= i;
    }
}
int findfather(int x){
    if(father[x]==x) return x;
    else return findfather(father[x]);
}

bool cmp(int a,int b){
    return a > b;
}

void Union(int a,int b){//
    int fa = findfather(a);
    int fb = findfather(b);
    if(fa>fb){
        father[fa] =fb;
    }else{
        father[fb] = fa;
    }
} 
int main(){
    scanf("%d",&n);
    init(n);
    for(int i = 1;i <= n;i++){//i为当前学生学号
        int k;
        int hobbyid;
        scanf("%d:",&k);
        for(int j = 0;j < k;j++){
            scanf("%d",&hobbyid);
            hobby[hobbyid].push_back(i);//i为当前学生学号
            //由于是从小到达扫描，所以所有vector数组已经排序完
        }
    }
    
    //将id更小的结点当作根结点
    //1.同类合并
    for(int i=1;i<=H-1;i++){
        if(hobby[i].size()>=2){//只有一共爱好超过2人才有意义
            for(int j = 0; j < hobby[i].size()-1;j++){//从1到n-1
                Union(hobby[i][j],hobby[i][j+1]);
                //这里容易出现漏点的情况
            }
        }
    }
    //2.路径压缩
    for(int i = 1;i<=n;i++){
        father[i] = findfather(i);
        cluter.insert(father[i]);
    }
    
    //输出
    printf("%d
",cluter.size());
    int c = 0;
    for(set<int>::iterator it =cluter.begin();it!=cluter.end();it++){
        int count =0;
        for(int j = *it;j <= n;j++){//如果没有将id更小的结点当作根结点的设定则需要从0开始扫
            if(father[j]==*it) count++;
        }

        cluter_count[c] = count;
        c++;
    }
    sort(cluter_count, cluter_count + c,cmp);

    for (int i = 0; i < c;i++){
        printf("%d", cluter_count[i]);
        if(i < c-1)
            printf(" ");
    }
    return 0;
}