L3-003. 社交集群

忘是亡心i 2022-05-31 09:15 167阅读 0赞

## L3-003. 社交集群 ##

题目链接：[L3-003. 社交集群][L3-003.]

时间限制
    1000 ms
    内存限制
    65536 kB
    代码长度限制
    8000 B
    判题程序
    Standard
    作者
    陈越

在社交网络平台注册时，用户通常会输入自己的兴趣爱好，以便找到和自己兴趣相投的朋友。有部分兴趣相同的人们就形成了“社交集群”。现请你编写程序，找出所有的集群。

**输入格式：**

输入的第一行给出正整数N（<=1000），即社交网络中的用户总数（则用户从1到N编号）。随后N行，每行按下列格式列出每个人的兴趣爱好：

Ki: hi\[1\] hi\[2\] … hi\[Ki\]

其中Ki（>0）是第i个人的兴趣的数量，hi\[j\]是第i个人的第j项兴趣的编号，编号范围为\[1, 1000\]内的整数。

**输出格式：**

首先在第一行输出整个网络中集群的数量，然后在第二行按非递增的顺序输出每个集群中用户的数量。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：
    8
    3: 2 7 10
    1: 4
    2: 5 3
    1: 4
    1: 3
    1: 4
    4: 6 8 1 5
    1: 4
    
    输出样例：
    3
    4 3 1

一开始看题，看到题目的时间限制：1000ms ，相对来说较宽松，感觉应该是用搜索做，但是看完题目后感觉就是一道查并集的题目啊。一开始想到对有相同兴趣的人进行查并集的合并操作，这种想法的代码如下：

// 对人进行查并集合并操作，集群祖先为人的编号
    // 24 分题解代码，最后两个测试点过不去，原因未知
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    using namespace std;
    
    const int MAXN = 1010;
    int root[MAXN];
    int high[MAXN];
    int interestHash[MAXN];
    int peopleSum[MAXN];
    
    int getRoot(int x) {
        return root[x] == x ? x : root[x]=getRoot(root[x]);
    }
    
    void merge(int x, int y) {
        int rX = getRoot(x);
        int rY = getRoot(y);
        if (rX != rY) {
            if (high[rX] < high[rY]) {
                root[rX] = rY;
            } else {
                root[rY] = rX;
                if (high[rX] == high[rY]) {
                    high[rX]++;
                }
            }
        }
    }
    
    void init() {
        memset(interestHash, -1, sizeof(int)*MAXN);
        for (int i = 0; i < MAXN; i++) {
            root[i] = i;
        }
    }
    
    int main() {
        init();
        int n, m, num;
        cin >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d:", &m);
            for (int j = 0; j < m; j++) {
                cin >> num;
                if (interestHash[num] != -1) {
                    merge(interestHash[num], i);
                } else {
                    interestHash[num] = i;
                }
            }
        }
    
        int setSum = 0;
        for (int i = 0; i < n; i++) {
            if (root[i] == i) {
                setSum++;
            }
            peopleSum[root[i]]++;
        }
        sort(peopleSum, peopleSum+n, greater<int>());
    
        cout << setSum << endl;
        for (int i = 0; i < setSum; i++) {
            if (i) {
                cout << " ";
            }
            cout << peopleSum[i];
        }
    
        return 0;
    }

提交发现最后两个测试点过不了。。。思前想后没想到原因。。。如果有大神知道还请告知。

后来换了一种思路：**对兴趣点进行查并集的合并操作。即在输入过程中不断的合并有共同兴趣点的兴趣点集合，并且将合并后的集合人数统计出来，之后就是排序什么的了。**

// 对兴趣点进行查并集操作，集合祖先为兴趣点编号 
    // 这种思路就对了，没搞明白上面的代码思路错哪里了。。。 
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 1010;
    // 记录兴趣点集合的祖先编号
    int interest[MAXN]; 
    // 记录每个集合树的高度，优化查并集操作的速度
    int high[MAXN];
    // 对应记录数组下标代表的兴趣点编号拥有的人数
    int people[MAXN];
    
    // 获取兴趣点编号为 x 的所在兴趣集合的祖先编号
    int getRoot(int x) {
        return x == interest[x] ? x : interest[x]=getRoot(interest[x]); 
    }
    
    // 合并两个编号为 x 和编号为 y 的兴趣点所在集合
    void merge(int x, int y) {
        int rootX = getRoot(x);
        int rootY = getRoot(y);
        if (rootX != rootY) {
            if (high[rootX] < high[rootY]) {
                interest[rootX] = rootY;
            } else {
                interest[rootY] = rootX;
                if (high[rootX] == high[rootY]) {
                    high[rootX]++;
                }
            }
        }
    }
    
    void init() {
        for (int i = 1; i < MAXN; i++) {
            // 初始状态，每个兴趣点集合祖先都是它本身
            interest[i] = i;
        }
    }
    
    int main() {
        init();
        int n, m, inte, inte1;
        cin >> n;
        for (int i = 0; i < n; i++) {
            scanf("%d: %d", &m, &inte);
            // 输入的过程中合并不同的兴趣点组成兴趣点集合
            for (int j = 1; j < m; j++) {
                scanf("%d", &inte1);
                merge(inte, inte1);
            }
            // 对应兴趣点集合的祖先所拥有的人数加一
            people[getRoot(inte)]++;
        }
        int setSum = 0, tempRoot;
        for (int i = 1; i < MAXN; i++) {
            tempRoot = getRoot(i);
            if (people[i]) {
                // 如果兴趣点编号等当前兴趣点集合祖先的编号，
                // 那么集群数量加一
                if (i == tempRoot) {
                    setSum++;
                } else {
                    // 否则就是某个兴趣点集合的子集，即为某个集群的子集，
                    // 那么对应的集群祖先拥有的人数就要加上当前兴趣点子集拥有的人数
                    people[tempRoot] += people[i];
                    people[i] = 0;
                }
            }
        }
        sort(people, people+MAXN, greater<int>());
    
        cout << setSum << endl;
        for (int i = 0; i < setSum; i++) {
            if (i) {
                cout << " ";
            }
            cout << people[i];
        }
    
        return 0;
    }

[L3-003.]: https://www.patest.cn/contests/gplt/L3-003