PAT Advanced 1107 Social Clusters

Overview

PAT advanced 1107 Social Clusters could be solved by using union-find algorithm with path compression optimization.

PAT Advenced 1107 Social Clusters Problem

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

PAT Advenced 1107 Social Clusters Algorithm

This problem is essential a problem of unin-find which is an algorithm to quikly determine whether two elements are in the same “set”. We can use the set to store the hobbies of each people, and just brute-forcely go over earch pair of people i, j to see if they have common intersetion of their hobby set, if so, we put them into the same union, path compression is used to optimize the performance.

The following C++ code is accepted by PAT OJ to solve this 1107 Social Clusters problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

using std::set;
using std::vector;
using std::map;

const int MAXN = 1001;
int p[MAXN];


void init(int n) {
	for (int i = 0; i < n; ++i) {
		p[i] = i;
	}
}

int find(int k) {
	return p[k] == k ? k : (p[k] = find(p[k]));
}

void connect(int i, int j) {
	p[find(i)] = p[find(j)];
}

bool intersection(const set<int> &s1, const set<int> &s2) {
	for (auto &e : s1) {
		if (s2.count(e) > 0) {
			return true;
		}
	}
	return false;
}

int main() {
	int n, k, h;
	vector<set<int>> hobs;

	scanf("%d", &n);
	hobs.resize(n);

	for (int i = 0; i < n; ++i) {
		scanf("%d:", &k);
		for (int j = 0; j < k; ++j) {
			scanf("%d", &h);
			hobs[i].insert(h);
		}
	}

	init(n);
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (intersection(hobs[i], hobs[j])) {
				connect(i, j);
			}
		}
	}

	map<int, int> clusters;
	for (int i = 0; i < n; ++i) {
		int c = find(i);
		if (clusters.find(c) == clusters.end()) {
			clusters[c] = 1;
		} else {
			clusters[c]++;
		}
	}
	vector<int> res;
	for(map<int,int>::iterator it = clusters.begin(); it != clusters.end(); ++it) {
	  res.push_back(it->second);
	}

	std::sort(res.begin(), res.end(), std::greater<int>());
	printf("%d\n", res.size());
	for (int i = 0, len = res.size(); i < len; ++i) {
		if (0 == i) {
			printf("%d", res[i]);
		} else {
			printf(" %d", res[i]);
		}
	}
	return 0;
}

Summary

PAT advanced 1107 Social Clusters is solved by using union-find algorithm with path compression optimization.

Written on June 19, 2016