算法练习4：并查集/连通图 1:知识点梳理

并查集：

并查集（Union-Find）是一种数据结构，用于处理不交集的合并和查询问题。它主要支持以下两种操作：

find：查找元素所在的集合（通常返回该集合的代表）。
union：将两个集合合并成一个集合。
下面是一个 Java 实现的并查集数据结构，包含路径压缩和按秩合并的优化：java

class UnionFind {private int[] parent; // 记录每个节点的父节点private int[] rank;   // 用于按秩合并的数组// 构造函数，初始化并查集public UnionFind(int size) {parent = new int[size]; // 初始化父节点数组rank = new int[size];   // 初始化秩数组for (int i = 0; i < size; i++) {parent[i] = i;      // 每个节点的父节点为自己rank[i] = 1;        // 初始秩为1}}// 查找根节点，并进行路径压缩public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩}return parent[x];}// 合并两个集合public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {// 按秩合并if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}// 判断两个元素是否在同一个集合中public boolean connected(int x, int y) {return find(x) == find(y);}
}

使用示例
下面是如何使用这个并查集实现的示例：java

public class Main {public static void main(String[] args) {UnionFind uf = new UnionFind(10); // 创建一个包含10个元素的并查集// 合并一些元素uf.union(1, 2);uf.union(2, 3);uf.union(4, 5);uf.union(6, 7);uf.union(5, 6);// 检查连接性System.out.println(uf.connected(1, 3)); // 输出 trueSystem.out.println(uf.connected(1, 4)); // 输出 falseSystem.out.println(uf.connected(5, 7)); // 输出 true// 合并两个集合uf.union(3, 4);// 再次检查连接性System.out.println(uf.connected(1, 4)); // 输出 true}
}

解释
路径压缩：在 find 方法中，通过递归更新每个节点的父节点到根节点，从而减少树的高度，使后续的查询更快。
按秩合并：在 union 方法中，通过比较两个根节点的秩，将较小的树合并到较大的树下，从而保持树的平衡，进一步提升操作效率。
这种实现的时间复杂度接近于常数（α(n)），其中 α 是阿克曼函数的逆，非常高效。