海南最新通知今天重要消息_小程序定制开发团队_小程序开发系统_站长之家查询工具

适用读者：初学算法与数据结构的 Java 开发者，或需要在工程中解决“动态连通性”问题的同学。
阅读收获：

1. 搞懂并查集背后的思想与两大经典优化；
2. 掌握一份可直接粘贴到项目里的 Java 代码；
3. 了解实际业务／竞赛里常见的应用场景与使用示例。

---

1 并查集是什么？

并查集（Disjoint-Set Union，简称 DSU 或 Union-Find）是一种 支持“分组”与“合并”操作 的树状数据结构，核心满足两件事：

操作	说明	均摊复杂度*
find(x)	查询元素 x 所在的集合代表（根节点）	α(n)
union(x, y)	合并 x 与 y 所在的两个集合	α(n)

* α(n) 是反阿克曼函数，在实际规模内几乎可以视作 O(1)。

为什么并查集能这么快？

• 路径压缩：find 时把搜索路径上的节点直接挂到根节点，下一次查找就更短。
• 按秩 / 按大小合并：union 时总是把“矮”的树或元素更少的集合挂到“高”的树下，最大深度保持对数级别。

---

2 它能解决哪些场景？

场景	问题本质
⛓ 图的动态连通性	动态添加边，实时判断两点是否连通
🌉 Kruskal 最小生成树	边按权排序时需要判断“是否会成环”
🕸 网络 & 社交关系	好友圈、局域网、服务器集群故障隔离
🔄 等价关系压缩	字符串同义、化学物质同分异构体归并
📸 图像分割	像素聚类成连通区域（Flood-Fill / 并行化）

---

3 数据结构设计

parent[]  // 下标即元素，值为父节点索引，根节点 parent[x] = x
size[]    // 可选：记录每棵树的节点数量（也可用 rank[] 记录高度）

• 初始化：parent[i] = i; size[i] = 1，每个元素自成单元素集合。
• find：递归或迭代向上走，结合路径压缩。
• union：先 find 两个根，如果不同，就按 size / rank 规则合并，同时更新 size。

---

4 Java 代码实现与详解

代码采用 路径压缩 + 按大小合并，兼顾可读性与性能。

/*** 并查集（DSU / Union-Find）* Author: WSKH0929*/
public class UnionFind {private final int[] parent;private final int[] size;   // 记录根节点的集合大小/** 构造函数：n 个元素编号 0 … n-1 */public UnionFind(int n) {parent = new int[n];size   = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;  // 每个节点的父亲先指向自己size[i]   = 1;  // 单元素集合大小为 1}}/** 查找根节点（带路径压缩）*/public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);  // 递归压缩路径}return parent[x];}/** 合并两个元素所在的集合，返回是否真的合并成功 */public boolean union(int x, int y) {int rx = find(x);int ry = find(y);if (rx == ry) return false;       // 已属于同一集合，无需合并// 小树挂到大树，保持近乎平衡if (size[rx] < size[ry]) {int tmp = rx; rx = ry; ry = tmp;}parent[ry] = rx;size[rx]  += size[ry];return true;}/** 判断两个元素是否在同一集合 */public boolean connected(int x, int y) {return find(x) == find(y);}/** 返回集合大小（仅根节点调用准确）*/public int size(int x) {int rx = find(x);return size[rx];}
}

关键代码逐行解释

1. 构造函数：一次性分配两条数组，O(n) 内存可控，避免使用 Map 带来的额外装箱与哈希开销。
2. find：递归写法简洁，JVM 对于小深度递归性能友好；若担心栈溢出可改为循环。
3. union：先比较 size，把小集合挂到大集合根上；两条语句同时更新父指针与大小，保持一致性。
4. 连接查询：连通性判断只需两次 find。
5. 复杂度：所有操作均为近似 O(1)，在百万级数据下依旧稳定。

---

5 复杂度与边界情况

维度	最坏复杂度	说明
时间 find / union	O(α(n))	α(n) ≈ 4 以下，几乎常数
空间	O(n)	两个 int[]，内存 = 8 × n 字节
边界	n = 1	退化为单元素集合，所有 union 均返回 false

Tips

• 若元素编号不连续，可先用 HashMap<Obj, Integer> 做映射再使用 DSU。
• 在并发环境中需加锁或使用并行 DSU（更高级话题，本文不展开）。

---

6 示例：动态判断图连通性

假设有 n 台服务器（0 ~ n-1），不断有连线操作 (a, b)，我们想实时判断所有机器是否最终被连成一个网络：

int n = 6;
UnionFind dsu = new UnionFind(n);
int[][] edges = {{0,1},{2,3},{1,2},{4,5},{3,4}};
for (int[] e : edges) {dsu.union(e[0], e[1]);if (dsu.size(0) == n) {          // 任意取 0 的集合大小 == n → 全网连通System.out.println("Now fully connected!");break;}
}

输出（第 4 次合并后）：

Now fully connected!

---

7 常见陷阱

1. 误用递归导致栈溢出

   • 对于 n ≈ 10^7 的极端数据，建议改成迭代 + 手动栈或尾递归优化。

2. 并发访问

   • 多线程下读写冲突会破坏树结构，可使用 线程局部并查集 或 锁分段 策略。

3. 忘记路径压缩／按秩合并

   • 两者缺一不可；只打开其中一个时性能可能退化到 O(n)。

4. 误用 size[idx]

   • 只有在 根节点 上读取 size 才准确，其他节点的 size 没有意义。