C++ 并查集解决社交网络问题：优化代码及解析

在之前的回复中，代码出现了一些错误，给您带来困扰，非常抱歉！以下是经过修正后的代码，并附带详细解析，希望对您有所帮助。

问题描述:

在社交网络中，用户之间可能存在朋友关系。我们需要编写一个程序，根据给定的朋友关系，计算出社交网络中最少的用户群体数量。

解题思路:

这个问题可以使用并查集算法高效解决。并查集可以快速地判断两个元素是否属于同一个集合，并合并不同的集合。

**代码实现:**cpp#include #include #include <unordered_map>

using namespace std;

// 查找元素所属的根节点int find(vector& parent, int x) { if (parent[x] == x) { return x; } return parent[x] = find(parent, parent[x]); // 路径压缩优化}

// 合并两个元素所在的集合void unionSets(vector& parent, int x, int y) { int rootX = find(parent, x); int rootY = find(parent, y); if (rootX != rootY) { parent[rootX] = rootY; }}

int main() { int m, n; // m 表示朋友关系的数量，n 表示用户的数量 cin >> m >> n;

vector<int> parent(n + 1); // 初始化并查集，每个节点的父节点初始为自身    for (int i = 1; i <= n; i++) {        parent[i] = i;    }

unordered_map<int, int> accountToRoot; // 记录每个账号对应的根节点

for (int i = 0; i < m; i++) {        int k; // 表示当前朋友关系涉及的用户数量        cin >> k;        int firstAccount; // 记录第一个用户的账号        cin >> firstAccount;        if (accountToRoot.find(firstAccount) == accountToRoot.end()) {            accountToRoot[firstAccount] = firstAccount; // 如果该账号未出现过，将其根节点设为自身        }        for (int j = 1; j < k; j++) {            int account;             cin >> account;            if (accountToRoot.find(account) == accountToRoot.end()) {                accountToRoot[account] = account; // 如果该账号未出现过，将其根节点设为自身            }            unionSets(parent, firstAccount, account); // 合并第一个用户和其他用户所在的集合        }    }

unordered_map<int, int> rootCount; // 统计每个根节点出现的次数    for (int i = 1; i <= n; i++) {        rootCount[find(parent, i)]++;     }

int minUsers = 0; // 统计最少的用户群体数量    for (auto it = rootCount.begin(); it != rootCount.end(); it++) {        if (it->second > 0) { // 如果一个根节点出现次数大于 0，则表示一个用户群体            minUsers++;        }    }

cout << minUsers << endl; // 输出最少用户群体数量

return 0;}

代码解析:

并查集初始化: 使用 vector<int> parent 存储每个节点的父节点，初始时每个节点的父节点都是自身。2. 处理朋友关系: 遍历所有朋友关系，使用 unionSets 函数将属于同一个朋友关系的用户合并到同一个集合中。3. 统计根节点: 遍历所有用户，使用 find 函数找到其所属的根节点，并统计每个根节点出现的次数。4. 计算用户群体数量: 遍历根节点计数器，统计出现次数大于 0 的根节点数量，即为最少的用户群体数量。

优化说明:

路径压缩: 在 find 函数中，每次查找时都将当前节点的父节点直接设置为根节点，减少后续查找的时间复杂度。

希望以上代码和解析能够帮助您理解并解决这个问题。如果您还有其他问题，请随时提出！