博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
程序设计基础80 并查集如何连结数据
阅读量:386 次
发布时间:2019-03-05

本文共 3901 字,大约阅读时间需要 13 分钟。

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:

83: 2 7 101: 42: 5 31: 41: 31: 44: 6 8 1 51: 4

Sample Output:

34 3 1

一,关注点

1,关于拥有相同爱好的两个人,如何连接?当时使用的是hobby的vector里添加人的方式,然后两两结合。这是比较直白的方式。

2,标准方法不是开vector来存储人,而是直接用数组来存储第一个有此爱好的人,以后的人都与这个人连接。这种方法简单。

二,我的代码

#include
#include
#include
using namespace std;const int max_n = 1100;int N = 0;int father[max_n];bool flag[max_n];int num_of_child[max_n];vector
vec[max_n];void init() { for (int i = 1; i <= N; i++) { father[i] = i; }}bool cmp(int a, int b) { return a > b;}int findFather(int x) { int a = x; while (x != father[x]) { x = father[x]; } while (a != father[a]) { int z = a; a = father[a]; father[z] = x; } return x;}void Union(int x, int y) { int faA = findFather(x); int faB = findFather(y); if (faA != faB) { father[faA] = faB; }}int main() { int num = 0, id = 0, num_of_circle = 0, max_id = -1; scanf("%d", &N); init(); for (int i = 1; i <= N; i++) { scanf("%d:", &num); for (int j = 0; j < num; j++) { scanf("%d", &id); vec[id].push_back(i); if (id > max_id) { max_id = id; } } } for (int i = 0; i <= max_id; i++) { int temp = vec[i].size(); for (int j = 0; j < temp - 1; j++) { Union(vec[i][j], vec[i][j + 1]); } } for (int i = 1; i <= N; i++) { flag[findFather(i)] = true; num_of_child[findFather(i)]++; } for (int i =1; i <= N; i++) { if (flag[i] == true) { num_of_circle++; } } sort(num_of_child + 1, num_of_child + N + 1, cmp); printf("%d\n", num_of_circle); for (int i = 1; i <= num_of_circle; i++) { printf("%d", num_of_child[i]); if (i != num_of_circle) { printf(" "); } } return 0;}

三,标准代码

#include
#include
using namespace std;const int max_n = 1010;int father[max_n] = { 0 };int group_num[max_n] = { 0 };bool flag[max_n] = { false };int course[max_n] = { 0 };int findFather(int x) { int a = x; while (x != father[x]) { x = father[x]; } while (a != father[a]) { int z = a; a = father[a]; father[z] = x; } return x;}void Union(int a, int b) { int faA = findFather(a); int faB = findFather(b); if (faA != faB) { father[faA] = faB; }}bool cmp(int a, int b) { return a > b;}int main() { int N = 0; scanf("%d", &N); for (int i = 1; i <= N; i++) { father[i] = i; } for (int i = 1; i <= N; i++) { int num = 0; scanf("%d:", &num); for (int j = 0; j < num; j++) { int hobby = 0; scanf("%d", &hobby); if (course[hobby] == 0) { course[hobby] = i; } Union(i, course[hobby]); } } for (int i = 1; i <= N; i++) { if (father[i] != 0) { flag[findFather(i)] = true; ++group_num[findFather(i)]; } } sort(group_num + 1, group_num + N + 1, cmp); int count = 0; for (int i = 1; i <= N; i++) { if (flag[i] == true)count++; } printf("%d\n", count); int num = 0; for (int i = 1; i <= N; i++) { if (group_num[i] != 0) { printf("%d", group_num[i]); num++; if (num != count) { printf(" "); } } } return 0;}

 

转载地址:http://nmlwz.baihongyu.com/

你可能感兴趣的文章