1107. Social Clusters (30)

时间限制 1000 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue

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 题目： 将有相同爱好的人归为一个cluster，输出有几个cluster，以及每个cluster有几个人 解法&&思路： 并查集，vis数组保存该爱好第一次出现在哪个人的名下，father数组记录谁和自己是一个cluster的 Code： #include <iostream> #include <vector> #include <algorithm> #include <string> #include <stdio.h> #include <math.h> #define MAXN 10003 using namespace std; int father[MAXN]; int vis[MAXN]; int FindRoot(int a) { while (father[a] != a) { a = father[a]; } return a; } void Union(int a, int b) { int a_root = FindRoot(a); int b_root = FindRoot(b); if (a_root != b_root) { father[a_root] = b_root; } } int main() { int n; std::cin >> n; for (int i = 0; i < MAXN; i++) { father[i] = i; vis[i] = -1; } for (int i = 0; i < n; i++) { int k; scanf("%d: ", &k); while (k--) { int p; std::cin >> p; p--; if (vis[p] == -1) { vis[p] = i; } else { Union(vis[p], i); } } } int count = 0; std::vector<int> fa; for (int i = 0; i < n; i++) { if (FindRoot(i) == i) { fa.push_back(i); count++; } } printf("%d\n", count); std::vector<int> cluster; for (int i = 0; i < fa.size(); i++) { count = 0; for (int j = 0; j < n; j++) { if (FindRoot(j) == fa[i]) { count++; } } cluster.push_back(count); } sort(cluster.begin(), cluster.end()); for (int i = cluster.size() - 1; i > 0; i--) { if (cluster[i] > 0) { printf("%d ", cluster[i]); } } if (cluster[0] > 0) { printf("%d", cluster[0]); } system("pause"); }