1107 Social Clusters （30 分)

When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:

Ki: hi[1] hi[2] ... hi[Ki]

where Ki (>) is the number of hobbies, and [ is the index of the j-th hobby, which is an integer in [1, 1000].

Output Specification:

For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in non-increasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

Sample Output:

3

4 3 1

思路：

有n个人，每个人喜欢k个活动，如果两个人有任意一个活动相同，就称为他们处于同一个社交网络。求这n个人一共形成了多少个社交网络。

#include <bits/stdc++.h>

using namespace std;

int p[],a[];

int n,k,m,h;

char c;

bool cmp(int a,int b)

{

    return a>b;

}

int found(int x)

{

    if(p[x] == x)

        return x;

    return found(p[x]);

}//found函数返回的是

void unite(int a,int b)

{

    int x = found(a);

    int y = found(b);

    if(x!=y)

    {

        p[y] = x;

    }

}//unite函数

int main()

{

    scanf("%d",&n);

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

        p[i] = i;

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

    {

        scanf("%d %c",&k,&c);

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

        {

            scanf("%d",&h);

            if(a[h] == )

            {

                a[h] = i;

            }

            else

            {

                unite(found(a[h]),i);

            }

        }

    }

    int cnt = ;

    int count1[] = {};

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

    {

        count1[found(i)]++;

    }

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

    {

        if(count1[i]!=)

            cnt++;

    }

    cout<<cnt<<endl;

    sort(count1+,count1+n+,cmp);

    for(int i=;i<=cnt;i++)

    {

        if(i==)

            cout<<count1[i];

        else

            cout<<" "<<count1[i];

    }

    return ;

}

巴特西

1107 Social Clusters （30 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章