A1107

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 (≤1000), 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:

K ​i ​​ : h ​i ​​ [1] h ​i ​​ [2] … h ​i ​​ [K ​i ​​ ]

where K ​i ​​ (>0) is the number of hobbies, and h ​i ​​ [j] 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:

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

Sample Output:

3
4 3 1

#include<bits/stdc++.h>
using namespace std;
struct people{
    vector<int>friends,hobby;
    int hobby_mp[1005];
}p[1005];
unordered_map<int,int>mp;
vector<int>ans;
int main(){
    int N;
    cin>>N;
    for(int i=1;i<=N;i++){
        int n,hobby;
        scanf("%d:",&n);
        for(int j=0;j<n;j++){
            scanf("%d",&hobby);
            p[i].hobby_mp[hobby]=1;
            p[i].hobby.push_back(hobby);
        }
    }
    for(int i=1;i<=N;i++){
        if(!mp[i]){
            for(int j=0;j<p[i].hobby.size();j++){           
                for(int k=1;k<=N;k++){  
                    if(p[k].hobby_mp[p[i].hobby[j]]&&mp[k]==0){
                        for(int l=0;l<p[k].hobby.size();l++)
                            if(p[i].hobby_mp[p[k].hobby[l]]==0) p[i].hobby.push_back(p[k].hobby[l]);
                        p[i].friends.push_back(k);
                        mp[k]=1;
                    }
                }
            }
            mp[i]=1;
            ans.push_back(p[i].friends.size());
        }
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(int i=ans.size()-1;i>=0;i--){
        printf("%d",ans[i]);
        if(i)printf(" ");
    }
    return 0;
}