(PAT)1107 Social Clusters (并查集)

忘是亡心i 2022-04-17 03:15 168阅读 0赞

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

解题思路:这题考察了并查集的使用

首先我们创建一个并查集,元素且根节点为人员编号,初始化的时候让各人员编号的父指针指向他自己

然后我们定义一个数组,让对应的爱好指向第一次选择这个爱号的人员编号

比如第一个人的爱好是2 7 10,那么对应的人员编号都是1

如果第二次出现了这个爱好,就让选择这个爱好的人作为第一次选这个爱好的人的子节点,插入到并查集中

最后统计并查集个数即可

1号喜欢2,7,10

2号喜欢4

3号喜欢5,3

它们之间没有共同喜欢的活动,因此分属三个不同的社交网络

4号喜欢4,所以和2同属一个网络

5号喜欢3,所以和3同属一个网络

代码:

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    const int maxn = 1010;
    int course[maxn] = { 0 };
    int isroot[maxn] = { 0 };
    bool dugroot[maxn] = { 0 };
    
    class DDJSSet {
    private:
    	int* father;   //用来保存每个结点的父结点
    	int* rank;     //用来保存每个结点的秩
    public:
    	DDJSSet(int size) {
    		father = new int[size+1];
    		rank = new int[size+1];
    		for (int i = 1; i <= size; ++i) {
    			father[i] = i;   //初始化时,将每个结点的父节点指向它自己
    			rank[i] = 0;
    		}
    	}
    
    	~DDJSSet() {
    		delete[] father;
    		delete[] rank;
    	}
    
    	int find_set(int node) {
    		if (father[node] != node) {
    			father[node] = find_set(father[node]);
    		}
    		return father[node];
    	}
    
    	void merge(int node1, int node2) {
    		int ancestor1 = find_set(node1);
    		int ancestor2 = find_set(node2);
    
    		if (ancestor1 != ancestor2) {   //如果不享有同一个公共结点的话
    			if (rank[ancestor1] > rank[ancestor2]) {   //将秩较小的结点指向秩较大的结点
    				swap(ancestor1, ancestor2);  //交换两个节点
    			}
    			father[ancestor1] = ancestor2; //将秩较小的结点指向秩较大的结点
    			rank[ancestor2] = max(rank[ancestor2], rank[ancestor1] + 1);
    		}
    	}
    };
    
    bool cmp(int a, int b) {
    	return a > b;
    }
    
    int main() {
    
    	DDJSSet dsu(maxn);
    	vector<int> res;
    
    	int n;
    	cin >> n;
    	for (int i = 1; i <= n; ++i) {   //一共有8个人
    		int h = 0;
    		scanf("%d:", &h);
    		for (int j = 0; j < h; ++j) {
    			int h = 0;
    			scanf("%d", &h);
    			if (course[h] == 0) {
    				course[h] = i;
    			}
    			dsu.merge(i, dsu.find_set(course[h]));
    		}
    	}
    
    	for (int i = 1; i <= n; ++i) {
    		int flag = dsu.find_set(i);
    		dugroot[flag] = true;
    		isroot[flag]++;
    	}
    
    	int ans = 0;
    	for (int i = 1; i <= n; ++i) {
    		if (dugroot[i]) {
    			ans++;
    			res.push_back(isroot[i]);
    		}
    	}
    	cout << ans << endl;
    	sort(res.begin(), res.end(), cmp);
    	for (auto k = 0; k < res.size(); ++k) {
    		if (k == res.size() - 1) {
    			cout << res[k];
    		}
    		else {
    			cout << res[k] << " ";
    		}
    	}
    
    	return 0;
    }