PAT (Advanced Level) Practice 1107 Social Clusters-蒲公英云

PAT (Advanced Level) Practice 1107 Social Clusters

傷城~ 2023-07-03 03:22 116阅读 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;
}