(PAT)1107 Social Clusters (并查集)-蒲公英云

(PAT)1107 Social Clusters (并查集)

忘是亡心i 2022-04-17 03:15 290阅读 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:

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;
}