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:
Ki: hi[1] hi[2] … hi[Ki]
where Ki (>0) is the number of hobbies, and hi[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
- 分析
很明显，这道题是考察并查集，但有点不同的是，反过来了，查的不是，hobby的分组，而是查人数的分组。反过来记录即可。
PAT_A1118那个查并集比较直接，不用在反转以下思维 - code
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
//f的下表为数据，内容为f
int f[1005];
int gf(int c)
{//这样更新有问题并不会使子孙直接指向最高的祖先//必须最后来一次全部的更新//或者在使用是调用该函数if(f[c]!=c) return f[c]=gf(f[c]);return c;
}
bool big(int a,int b){
return a>b;}
int main()
{int n=0;//方便我们最好的查找计算memset(f,0,sizeof(f));cin>>n;//由于最后是求人数，即是将人分组vector<int>in[1005];vector<int>d;d.assign(n,-1);for(int i=0;i<n;i++){int hobs=0;scanf("%d:",&hobs);for(int j=0;j<hobs;j++){int hob=0;cin>>hob;//很有意思，我们分组的是人数in[hob].push_back(i);}}for(int i=0;i<n;i++)f[i]=i;for(int i=0;i<1005;i++){if(in[i].size()==0)continue;//i号hob,人数分组合并int u=gf(in[i][0]);for(int j=1;j<in[i].size();j++){int v=gf(in[i][j]);//这还必须是这样，归一//如果u是变化的，一直指向v的前一个，则谁赋给谁是无所谓的//由于u是固定的，只能改变f[v]的值，才能确保这一组有一个共同的父亲if(u!=v)f[v]=u;//是错误的，不能保证有同一个父亲//if(u!=v)f[u]=v;}}//更新f,使其直接指向父亲for(int i=0;i<n;i++)gf(i);vector<int>out;out.assign(n,0);//上边已经更新，这就没必要了调用函数了，其实调用也就多了一步//for(int i=0;i<n;i++)out[gf(i)]++;for(int i=0;i<n;i++)out[f[i]]++;sort(out.begin(),out.begin()+out.size(),big);int count=0;//人数是连续的，这对循环来说不用再加控制了for(int i=0;i<n;i++){if(out[i]==0)continue;count++;}cout<<count<<endl;for(int i=0;i<n;i++){if(out[i]>0)cout<<out[i];if(out[i+1]>0)cout<<" ";if(out[i+1]==0){cout<<endl;break;}}return 0;
}