GPLT L3-003 社交集群

题述

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式

输入在第一行给出一个正整数 $N(\le1000)$ ，为社交网络平台注册的所有用户的人数。于是这些人从 $1$ 到 $N$ 编号。随后 $N$ 行，每行按以下格式给出一个人的兴趣爱好列表：

$K_i: h_i[1] \ h_i[2] \ \cdots \ h_i[K_i]$

其中 $K_i(\gt0)$ 是兴趣爱好的个数， $h_i[j]$ 是第 $j$ 个兴趣爱好的编号，为区间 $[1, 1000]$ 内的整数。

输出格式

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

输入样例

输出样例

1
2

3
4 3 1


代码长度限制	16 KB
时间限制	300 ms
内存限制	64 MB
栈限制	8192 KB

代码实现

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x = 0;
    while (!isdigit(cin.peek())) cin.ignore();
    while (isdigit(cin.peek())) x = (x << 3) + (x << 1) + (cin.get() ^ 48);
    return x;
}
class UnionFind {
private:
    unordered_map<int, int> parent;
public:
    bool exist(int a) {
        return parent.count(a);
    }
    int find(int a) {
        return parent[a]
            = (!exist(a) || parent[a] == a)
            ? a : find(parent[a]);
    }
    void unite(int a, int b) {
        if (find(a) != find(b))
            parent[find(a)] = find(b);
    }
    vector<unordered_set<int>> groups() {
        vector<unordered_set<int>> res; // 获取所有子集
        unordered_map<int, unordered_set<int>> mp;
        for (auto& [i, p]: parent) mp[p].insert(i);
        for (auto& [i, p]: mp) res.emplace_back(p);
        sort(begin(res), end(res), // 按子集大小降序排列
             [](auto&a,auto&b){return a.size()>b.size();});
        return res;
    }
};
int main() {
    int n = read();
    unordered_map<int, unordered_set<int>> mp_i2p, mp_p2i;
    for (int p = 1; p <= n; p++) {
        int k = read();
        while (k--) {
            int i = read();
            mp_i2p[i].insert(p); // 兴趣到人的映射
            mp_p2i[p].insert(i); // 人到兴趣的映射
        }
    }

    UnionFind uf;
    auto bfs = [&](int p){
        queue<int> q; q.push(p);
        while (!q.empty()) {
            for (auto& i: mp_p2i[q.front()]) {  // 遍历此人的兴趣
                for (auto& ip: mp_i2p[i]) {     // 遍历同兴趣的人
                    if (uf.exist(ip)) continue; // 跳过已加入的人
                    uf.unite(ip, p);            // 将 ip 并到 p
                    q.push(ip);
                }
            }
            q.pop();
        }
    };
    for (int p = 1; p <= n; p++)
        if (!uf.exist(p))
            bfs(p); // 对未加入集群的人进行BFS

    auto ve = uf.groups();
    cout << ve.size();
    for (auto& it: ve) {
        if (&it == &ve.front()) cout.put(0xA);
        else cout.put(0x20); cout << it.size();
    } cout.put(0xA);
    return 0;
}

代码解析

通过结合 并查集（Union-Find） 和 广度优先搜索（BFS） 高效划分社交集群，核心逻辑分为以下步骤：

数据结构设计

并查集类（UnionFind） 维护用户间的集合关系，提供以下操作：
- exist：判断用户是否在并查集中。
- find：查找根节点，带路径压缩。
- unite：合并两个集合。
- groups：统计所有集群并按大小降序排列。
双向映射表 构建两个哈希表：
- mp_i2p：兴趣到用户的映射，便于快速查找共享兴趣的用户集合。
- mp_p2i：用户到兴趣的映射，记录每个用户的兴趣列表。

输入预处理

读取每个用户的兴趣，填充上述双向映射表。
例如，若用户1的兴趣为[2, 7, 10]，则：
- mp_i2p[2] 、 mp_i2p[7] 和 mp_i2p[10] 均添加用户1。
- mp_p2i[1] 添加兴趣2、7和10。

社交集群发现

通过 BFS 遍历未处理的用户，并利用 并查集 动态合并集群：

启动点选择
- 对于每个未被处理的用户（未在并查集中），作为当前集群的起点。
广度优先扩展
1. 遍历当前用户的所有兴趣，找到共享这些兴趣的其他用户。
2. 将这些用户与当前用户合并至同一集群，并将他们加入队列。
3. 递归处理队列中的用户，直到所有与该集群关联的用户均被合并。
合并逻辑
1. 若用户B与用户A有共同兴趣，用户B会被合并到用户A的集群。
2. 若用户C与用户B有共同兴趣，用户C也会被并到用户A的集群。
3. 最终用户A、B、C形成一个集群。

结果统计与输出

获取所有集群：调用 groups() 方法，按集群规模降序排列。
按格式输出：第一行为集群总数，第二行为各集群成员数目的降序列表。

示例分析

以输入样例为例

程序执行步骤

构建映射
1. 例如，兴趣4对应用户2、4、6、8。
处理用户
1. 用户1单独一个集群。
2. 用户2、4、6、8被合并到同一集群（共享兴趣4）。
3. 用户3、5、7被合并到同一集群（共享兴趣3或5）。
输出结果
1. 集群数3（大小4、3、1），符合预期。

通过上述流程，程序高效识别了所有潜在社交集群。