并查集用数组parent[]实现，初始时parent[i]=i；通过find找根节点、union合并集合来维护连通性，构造函数初始化各元素为独立集合。
在 java 中用数组实现并查集（union-find）是理解其原理和解决动态连通性问题最直接的方式。核心思想是用一个整型数组 parent[] 表示每个元素的父节点，初始时每个元素自成一个集合（即 parent[i] = i），再通过 find 查找根节点、union 合并集合来维护连通关系。
基础结构与初始化
定义一个类（如 UF），内部维护数组 parent 和元素总数 n。构造函数将每个索引初始化为自身，表示初始时所有元素互不连通：
// 示例：支持 0 到 n-1 的整数节点
private int[] parent;<br>
public UF(int n) {<br>
this.parent = new int[n];<br>
for (int i = 0; i
parent[i] = i;<br>
}<br>
}
查找根节点（带路径压缩）
find 方法用于判断两个节点是否连通——本质是比较它们的根是否相同。为提升效率，采用路径压缩：在递归或迭代回溯时，把沿途所有节点直接挂到根下。
public int find(int x) {<br>
if (parent[x] != x) {<br>
parent[x] = find(parent[x]); // 递归压缩<br>
}<br>
return parent[x];<br>
}
说明：
• 若不用递归，也可用循环先找根，再遍历路径统一赋值；
• 路径压缩不改变连通性，但显著降低后续 find 的平均时间复杂度（接近常数）。
合并两个集合（按秩/大小合并可选）
union 方法将两个元素所在集合合并。最简实现是让一个根指向另一个根：
public void union(int p, int q) {<br>
int rootP = find(p);<br>
int rootQ = find(q);<br>
if (rootP == rootQ) return;<br>
parent[rootP] = rootQ; // 或 parent[rootQ] = rootP<br>
}
进阶建议（提升性能）：
• 引入 size[] 数组记录各树节点数，总是把小树挂到大树下（避免退化为链表）；
• 或引入 rank[] 记录树高度，按秩合并（仅在秩相同时才增加目标秩）；
• 即使只做简单合并，配合路径压缩，也能达到极佳的实际性能。
判定连通性与使用示例
连通性判定只需调用 find(p) == find(q)。例如处理图的边连接问题：
UF uf = new UF(10);<br> uf.union(0, 1);<br> uf.union(1, 2);<br> uf.union(3, 4);<br> System.out.println(uf.connected(0, 2)); // true<br> System.out.println(uf.connected(0, 3)); // false
注意：
• 并查集不支持删除操作或获取具体连通分量内容；
• 若需统计连通分量数量，可额外维护一个 count 变量，每次成功 union 后减一；
• 所有操作均基于整数索引，实际使用中需做好业务 ID 到数组下标的映射（如用哈希表预处理）。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
