PAT甲级1107. Social Clusters
题意:
当在社交网络上注册时,您总是被要求指定您的爱好,以便找到一些具有相同兴趣的潜在朋友。一个“社会群体”是一群拥有一些共同兴趣的人。你应该找到所有的集群。
输入规格:
每个输入文件包含一个测试用例。对于每个测试用例,
第一行包含一个正整数N(<= 1000),一个社交网络中的总人数。因此,人数从1到N.然后N行跟随,每个给出一个人的爱好列表的格式:
Ki:hi [1] hi [2] ... hi [Ki]
其中Ki(> 0)是兴趣的数量,hi [j]是第j个兴趣的指数,
这是[1,1000]中的整数。
输出规格:
对于每种情况,在一行中打印网络中的集群总数。然后在第二行,以不增加的顺序打印群集中的人数。这些数字必须被一个空格分开,而行的末尾必须没有额外的空格。
思路:
并查集
ac代码:
C++
// pat1107.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<stdio.h>
#include<map>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
using namespace std;
const int maxn = 1002;
int n;
unordered_map<int, int> cluster;
int person_cnt[maxn];
int pre[maxn];
int find(int x)
{
return pre[x] == x ? x : find(pre[x]);
}
void insert(int x, int y)
{
int xx = find(x);
int yy = find(y);
if (xx == yy) return;
pre[yy] = xx;
}
bool cmp(const int a, const int b)
{
return a > b;
}
int main()
{
scanf("%d", &n);
int num,ho,cnt = 1;
for (int i = 1; i < maxn; i++)
{
pre[i] = i;
}
for (int i = 0; i < n; i++)
{
int where = -1;
scanf("%d:", &num);
vector<int> hobby(num);
for(int j = 0; j < num; j++)
{
scanf("%d", &hobby[j]);
if (cluster.find(hobby[j]) != cluster.end())
{
if(where == -1)
where = cluster[hobby[j]];
else
{
insert(where, cluster[hobby[j]]);
}
}
}
if (where == -1)
{
for (int u = 0; u < num; u++)
cluster[hobby[u]] = cnt;
person_cnt[cnt]++;
cnt++;
}
else
{
for (int u = 0; u < num; u++)
cluster[hobby[u]] = where;
person_cnt[where]++;
}
}
cnt--;
int res_cnt = 0;
vector<int> res;
for (int i = 1; i <= cnt; i++)
{
if(pre[i] != i)
person_cnt[find(i)] += person_cnt[i];
}
for (int i = 1; i <= cnt; i++)
{
if (pre[i] == i)
{
res_cnt++;
res.push_back(person_cnt[i]);
}
}
printf("%d
", res_cnt);
sort(res.begin(), res.end(),cmp);
for (int i = 0; i < res_cnt - 1; i++)
printf("%d ", res[i]);
printf("%d
", res[res_cnt - 1]);
return 0;
}