GPTL L3-003 社交集群（并查集）

数据有些弱，Union函数不判不等也可以过。

题意：

依次给出 n 个人的兴趣，不同人兴趣相交、不同兴趣所属人员相交均属于同一集群，求形成的不相交集群个数及每个集群的人数。

思路：

枚举每个兴趣的人员，以序号最小者作为集群代表与其他成员合并，追加 cnt 数组记录每个集群的人数。

如题目输入：

1	2	3	4	5	6	7	8	9	10
7	1	3	2	3	7	1	7		1
		5	4	7		3
			6
			8

则存在 ( 2, 4, 6, 8 )、( 3, 5, 7 )、( 1 )三个集群。

Tips：

注意读入输入中的 '：'。

#include <bits/stdc++.h>

using namespace std;

const int M=1100;

int fri[M],cnt[M];

vector<int> like[M];

int Find(int x){

    int f=x;

    while(f!=fri[f]) f=fri[f];

    int a=x,b;

    while(a!=fri[a]) b=fri[a],fri[a]=f,a=b;

    return f;

}

void Union(int A,int B){

    int friA=Find(A);

    int friB=Find(B);

    if(friA!=friB)

        fri[friB]=friA,cnt[friA]+=cnt[friB];//friA一定小于friB

}

int main()

{

    for(int i=0;i<M;i++) fri[i]=i,cnt[i]=1;

    int n;cin>>n;

    for(int i=1;i<=n;i++){

        int k;char c;cin>>k>>c;

        for(int j=0;j<k;j++){

            int t;cin>>t;

            like[t].push_back(i);

        }

    }

    for(int i=0;i<M;i++){

        if(like[i].size()>=2){

            for(int j=1;j<like[i].size();j++){

                Union(like[i][0],like[i][j]);

            }

        }

    }

    vector<int> ans;

    for(int i=1;i<=n;i++)

        if(fri[i]==i) ans.push_back(cnt[i]);

    sort(ans.begin(),ans.end(),greater<int>());

    cout<<ans.size()<<endl;

    for(int i=0;i<ans.size();i++)

        cout<<(i?" ":"")<<ans[i];

    return 0;

}

巴特西

GPTL L3-003 社交集群（并查集）

题意：

思路：

Tips：

最新文章

热门文章