原神，启动！（并查集分组问题）

我们将深入探讨如何通过 并查集（Union-Find）解决一道经典的分组问题。问题来源于一个有趣的场景——原神玩家阿政希望将朋友分组，而朋友之间的认识关系决定了分组的方式。让我们通过这道题目来学习如何高效地解决类似问题。

问题描述

阿政有若干朋友，其中某些朋友彼此认识，认识关系是互通的。如果 A 认识 B，B 认识 C，那么可以认为 A、B、C 彼此认识，可以组成一个小组。阿政想知道，至少需要将朋友分成多少组，保证每组中的朋友都互相认识。

输入格式

输出格式

对于每个测试用例，输出至少需要分成的组数。

示例

输入：

2
5 3
1 2
2 3
4 5

5 1
2 5

输出：

2
4

解题思路

为了解决这个问题，可以将朋友的认识关系看成一个 无向图，朋友是图的节点，认识关系是图的边。问题就转化为：

并查集简介

并查集是一种非常高效的数据结构，用于处理动态连通性问题。它支持两个主要操作：

1. 查找（Find）：确定某个节点所属的连通分量。
2. 合并（Union）：将两个节点所在的连通分量合并成一个。

此外，使用路径压缩和按秩合并优化后，并查集的时间复杂度几乎是常数级别，适合处理大规模数据。

算法流程

1. 初始化：每个节点初始属于不同的连通分量。
2. 合并操作：对于每一条边，将两个节点所在的连通分量合并。
3. 统计结果：遍历所有节点，统计连通分量的数量。

代码实现

以下是使用 C++ 并查集解决问题的完整代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int p[N];

// 查找函数，带路径压缩
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}

// 合并两个连通分量
void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx != fy) {
        p[fy] = fx;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        // 初始化并查集
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        
        // 读取认识关系并合并
        while (m--) {
            int x, y;
            cin >> x >> y;
            unite(x, y);
        }
        
        // 统计连通分量
        unordered_map<int, int> group;
        int count = 0;
        
        for (int i = 1; i <= n; i++) {
            int fi = find(i);
            if (group[fi] == 0) {
                count++;
                group[fi] = 1;
            }
        }
        
        cout << count << '\n';
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：

  • 初始化：O(N)
  • 合并操作：O(M * α(N))，其中 α(N) 是阿克曼函数的反函数，接近常数。
  • 统计连通分量：O(N) 总体复杂度为 O(T * (N + M))。

• 空间复杂度：O(N)，用于存储并查集数组。

总结

通过并查集，我们成功解决了一个动态连通性问题。这种方法不仅适用于本题，还能扩展到社交网络、岛屿计数等众多领域。如果你对图论感兴趣，可以尝试将本题的解决方法迁移到更多复杂场景中。