本文共 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/