PAT甲级1107 Social Clusters 1、4样例没过解析

妖狐艹你老母 2023-02-22 05:27 8阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70][]

观察样例，发现A、B、C三人，即使A和C并没有共同爱好，但他们和B都有共同爱好，所以他们也属于同一个集合

因此我考虑将有关联的爱好捆绑在一起：合并一个人的所有爱好，只要A和B的爱好有交集，那么他们的所有爱好都会被绑定到一个集合中

统计人数时，取每个人的第一个爱好（题目保证每个人至少一个爱好），找到该爱好所属的集合的根，将根的值放入result,累加一次num\[r\]；最后将每个集合对应的人数放入out，排序一下输出即可

但是提交后发现，1、4样例无法通过，检查了半天思路并没有问题啊...很纳闷，最后无意中看到合并操作时打字打错了，本来应该是当两个节点不属于一个集合中时，令b的根指向a（纯属打字错误，给自己长个记性，敲的时候一定要多检查，等全写好了，错在哪里都不知道....）

![20200702092121571.png][]

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int father[1005];
    int num[1005]={0};
    int ff(int a)
    {
        int x=a;
        while(a!=father[a])
        {
            a=father[a];
        }
        while(x!=father[x])
        {
            int c=x;x=father[x];father[c]=a;
        }
        return a;
    }
    void nion(int a,int b)
    {
        int fa=ff(a),fb=ff(b);
        if(fa!=fb)father[fb]=a;
    }
    int main()
    {
        int n,k;
        cin>>n;
        vector<int> v[1005];
        for(int i=0;i<1005;i++)father[i]=i;
        for(int i=1;i<=n;i++)
        {
            cin>>k;
            int temp,p;
            getchar(); 
            cin>>temp;
            v[i].push_back(temp);
            for(int j=1;j<k;j++)
            {
                cin>>p;
                nion(temp,p);
            }
        }
        vector<int> result,out;//result存储每个根节点下标
        for(int i=1;i<=n;i++)
        {
            int r=ff(v[i][0]);
            if(num[r]==0)result.push_back(r);
            num[r]++;
        }
        for(int i=0;i<result.size();i++)out.push_back(num[result[i]]);
        sort(out.begin(),out.end());
        cout<<result.size()<<endl;
        for(int i=out.size()-1;i>=0;i--)
        {
            if(i!=0)cout<<out[i]<<" ";
            else cout<<out[i]<<endl;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200702090755607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70
[20200702092121571.png]: https://img-blog.csdnimg.cn/20200702092121571.png