【PAT】A1107 Social Clusters (30分)

1107 Social Clusters (30分)

题目链接

基本思路如下：
1.首先确定算法，典型的并查集；
2.把每一个network合并到一块；
3.计算每一个network的“根节点”，“根节点”地值，即为该network所包括的人数；
4.统计。

#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 1005;
int father[maxn];
int isRoot[maxn];
int arr[maxn];void init()
{
    for(int i=0;i<maxn;i++){
    father[i] = i;isRoot[i] = 0;}}int findFather(int x)
{
    int a = x;while(x != father[x])x = father[x];while(a != father[a]){
    int z = a;a = father[a];father[z] = x;}return x;
}void Union(int a, int b)
{
    int faA = findFather(a);int faB = findFather(b);if(faA != faB)father[faA] = faB;
}int cmp(int &a, int &b)
{
    return a > b;
}int main()
{
    init();int n;cin>>n;for(int i=0;i<n;i++){
    int k, h1;scanf("%d:%d",&k, &arr[i]);for(int j=1;j<k;j++){
    cin>>h1;Union(arr[i], h1);//步骤2}}int counts = 0;for(int i=0;i<n;i++)isRoot[findFather(arr[i])]++;//步骤3sort(isRoot, isRoot + maxn, cmp);for(int i=0;i<maxn;i++){
    if(isRoot[i])counts++;//步骤4elsebreak;}cout<<counts<<endl;for(int j=0;j<counts;j++){
    if(j!=0)cout<<" ";cout<<isRoot[j];}cout<<endl;return 0;
}