并查集
一、核心思想
并查集（Union-Find）是一种处理不相交集合合并与查询的高效数据结构，核心功能包括：
- 合并（Union）：将两个不相交集合合并为一个集合。
- 查询（Find）：判断两个元素是否属于同一集合。
核心优化手段：
- 路径压缩（Find时优化）：缩短查找路径，直接指向根节点。
- 按秩合并（Union时优化）：根据树高或集合大小决定合并方向，避免树过高退化。
二、Java模板代码
Javapublic class UnionFind {private int[] parent; // 父节点数组private int[] rank; // 秩（树高或集合大小）用来优化集合树的高度// 初始化：每个元素自成一个集合public UnionFind(int n) {parent = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 1; // 初始秩为1}}// 路径压缩查找（递归实现）public int find(int x) {if (parent[x] == x) return parent[x];return parent[x] = find(parent[x]); // 路径压缩核心}//未优化的查找算法public int find(int x) {if (parent[x] == x) return parent[x];return find(parent[x]);}// 按秩合并public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) return;// 按秩合并逻辑if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++; // 秩相同时合并后秩+1}}
}
三、优化点解析
路径压缩
return parent[x] = find(parent[x]); // 路径压缩核心
-
目的：缩短查找路径，使树扁平化。
-
实现：在递归查找时，将当前节点的父节点直接指向根节点。
-
效果：均摊时间复杂度接近 O(α(n))（阿克曼函数的反函数，增长极慢）
按秩合并
if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++; // 秩相同时合并后秩+1}
秩的定义与合并规则
-
秩的含义：秩表示以当前节点为根的树的高度（或深度）上界。例如，初始时每个元素的秩为1（单节点树的高度为1）
-
合并策略：
-
若两树秩不同：将秩较小的树的根节点指向秩较大的树的根节点。此时，合并后的树高度由较大秩决定，因此
无需增加秩
-
若两树秩相同：将其中一个根节点指向另一个根节点，此时合并后的树高度会增加1，因此需将新根的秩加1
因为原来的高度是相同的,一旦有一棵树的根节点指向另外一个根节点就会使这个合体树多一层,大树吃小树是不会影响深度的,因为是将一颗树的根节点指向另一颗树的根节点
-
相比与按大小合并的优势
[参考文章](并查集 rank 的优化 | 菜鸟教程)
基于 size 的优化在某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。
根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操作完后，层数变为4，比之前增多了一层，如下图所示：
由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这就是基于 rank 的优化。
