PAT (Advanced Level) Practice 1107 Social Clusters

傷城~ 2023-07-03 03:22 35阅读 0赞

解题方法：**并查集**。  
把爱好当成并查集元素。  
**对于每个人**  
当爱好只有一个时，不做任何操作。  
当爱好大于一个时，两两进行并查集的合并操作。

遍历完后，就可找出，每个cluster的father (father\[i\]=i)  
但是有一个问题：我们为了方便编码，会开辟father\[1001\] 大小的数组，来记录第 i 个元素的father，初始化时 father\[i\] = i，  
可能爱好 i 并不存在，但是也有father\[i\]=i。所以我加了个exist数组来记录爱好 i 是否存在。  
所以 i 是一个cluster 的根的判别条件为 father\[i\]==i && exist\[i\]==true。

**还有一个问题，如何知晓每个cluster的人数呢?**  
我这里用了一个hobby数组，记录第i个人的第一个爱好（每个人至少有一个爱好）  
还有一个number数组，记录以 i 为根的cluster 的人数。  
接下来遍历hobby数组，对于每个爱好可以找到他的根root，再令number\[root\]++，即可。  
  
最后排序输出就完事了。  
  
总结：这道题时限是1200ms，但是用并查集3、4ms就可以过，为啥要给这么长时间呢？其实PAT题目做多了，就知道，放宽时间，是为了给暴力解题（或者算法不是很优）的人点分拿。往往最优的代码在很短的时间内就能过，而不那么好的代码，可能会超时1、2个用例。

#include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <vector>
    #define maxn 1001
    using namespace std;
    vector<int> cluster;
    int father[maxn],number[maxn]={0},hobby[maxn];
    bool exist[maxn]={false};
    int findfather(int a){
        int z = a;
        while(a!=father[a]){
            a = father[a];
        }
        while(z!=father[z]){
            int m = z;
            z=father[z];
            father[m]=a;
        }
        return a;
    }
    void unio(int a,int b){
        int fa=findfather(a);
        int fb = findfather(b);
        if(fa!=fb){
            father[fb]=fa;
        }
    }
    int main()
    {
        for(int i=0;i<maxn;i++){
            father[i]=i;
        }
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            int k,a,b;
            scanf("%d: %d",&k,&a);
            hobby[i]=a;
            exist[a]=true;
            if(k>1){
                for(int i=1;i<k;i++){
                    scanf("%d",&b);
                    exist[b]=true;
                    unio(a,b);
                    a=b;
                }
            }
        }
        for(int i=0;i<n;i++){
            int f = findfather(hobby[i]);
            number[f]++;
        }
        for(int i=1;i<maxn;i++){
            if(exist[i]==true&&father[i]==i){
                cluster.push_back(number[i]);
            }
        }
        sort(cluster.begin(),cluster.end());
        cout<<cluster.size()<<endl;
        for(int i=cluster.size()-1;i>=0;i--){
            cout<<cluster[i];
            if(i!=0) cout<<" ";
        }
        return 0;
    }