本文共 2070 字，大约阅读时间需要 6 分钟。
并查集（Union-Find）是一种高效的数据结构，广泛用于解决并查集操作的时间复杂度问题。在这个问题中，我们需要实现并查集算法，并通过代码来展示其工作原理。
并查集的实现
并查集的核心思想是通过路径压缩和按秩合并两个操作来保持数据结构的高效性。路径压缩将节点直接指向根节点，减少查找时间；按秩合并则确保小树合并到大树中，保持树的平衡。
数据结构
父指针数组：用于记录每个节点的父节点，根节点的父指针指向自身。 计数器数组：用于记录每个根节点的子树大小。 初始化
- 创建父指针数组和计数器数组。
- 每个节点最初都是自己的父节点，计数器初始化为1。
查找操作
查找函数用于找到节点的根节点：
int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]);} 路径压缩技术确保查找操作的时间复杂度接近常数。
合并操作
合并函数用于将两个节点合并到同一集合中：
void joint(int x, int y) { if (find(x) == find(y)) return; if (cnt[find(x)] > cnt[find(y)]) { par[find(y)] = find(x); cnt[find(x)] += cnt[find(y)]; } else { par[find(x)] = find(y); cnt[find(y)] += cnt[find(x)]; }} 按秩合并确保小树合并到大树中，保持树的高度较低。
代码实现
#include #include using namespace std;const int MAX_N = 2e5 + 5;int par[MAX_N], cnt[MAX_N];unordered_map umap;void init(int n) { for (int i = 0; i < n; ++i) { par[i] = i; cnt[i] = 1; }}int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]);}void joint(int x, int y) { if (find(x) == find(y)) return; if (cnt[find(x)] > cnt[find(y)]) { par[find(y)] = find(x); cnt[find(x)] += cnt[find(y)]; } else { par[find(x)] = find(y); cnt[find(y)] += cnt[find(x)]; }}int main() { int T; cin >> T; while (T--) { int n; cin >> n; int cntv = 0; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; if (umap.find(x) == umap.end()) { ++cntv; umap[x] = cntv; } if (umap.find(y) == umap.end()) { ++cntv; umap[y] = cntv; } joint(umap[x], umap[y]); } int result = 0; for (int i = 0; i <= cntv; ++i) { result = max(result, cnt[find(i)]); } cout << result << endl; } return 0;}
代码解释
初始化：init函数初始化父指针和计数器数组。 查找：find函数使用路径压缩技术找到节点的根节点。 合并：joint函数按秩合并两个节点，确保树的平衡。 主函数：读取输入数据，处理每个数对，计算并查集的高度并输出结果。 通过上述代码，我们可以高效地实现并查集算法，解决并查集操作的时间复杂度问题。
转载地址：http://hsbiz.baihongyu.com/