一、认识并查集
1. 并查集的定义
并查集（Disjoint Set）是一种用于管理不相交集合的数据结构。它主要用于处理需要动态维护集合合并和查询操作的问题。其核心功能高效支持两个基本操作：
Find（查找）：确定某个元素属于哪一个集合。 Union（合并）：将两个元素所在的集合合并为一个集合。
2. 基本概念
2.1. 集合的表示
并查集通常通过一个数组（parent 数组）来表示每个元素的'父节点'，从而形成森林结构。每个集合用一棵树表示，树的根节点即为该集合的代表元素。
例如，假设有 5 个元素（0, 1, 2, 3, 4），初始时每个元素都是一个独立的集合：
0 1 2 3 4
对应的 parent 数组为 [0, 1, 2, 3, 4]，每个元素的父节点指向自己。
2.2. 合并操作
当需要将两个元素所在的集合合并时，可以将其中一个集合的根节点指向另一个集合的根节点。例如，将元素 1 和元素 0 所在的集合合并：
此时 parent 数组变为 [1, 1, 2, 3, 4]，元素 1 和 0 属于同一个集合，根节点是 1。
2.3. 查询操作
查询某个元素属于哪个集合时，只需找到该元素所在树的根节点。例如，查询 find(0) 会沿着父节点链向上直到根节点。
3. 基本操作实现
3.1. 初始化
初始化时，每个元素的父节点指向自己，秩（rank）初始化为 0。
public 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] = 0;
}
}
}
3.2. 查找（带路径压缩）
查找操作的目的是找到根节点。为了提高效率，使用路径压缩技术，将查找路径上的所有节点直接指向根节点。
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
3.3. 合并（带按秩合并）
合并时将两个集合的根节点连接。为了避免树变得过高，通常使用按秩合并策略，将秩较小的树合并到秩较大的树上。
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] += 1;
}
}
}
4. 优化技巧详解
4.1. 路径压缩
在 find 操作中，递归返回时将沿途节点的父节点直接设为根节点。这大大减少了后续查找的深度，使得单次操作的时间复杂度接近常数。
4.2. 按秩合并
维护每个树的高度（秩）。合并时总是将矮树挂到高树下，保证树的高度增长缓慢。结合路径压缩后，时间复杂度可降至 O(α(n))，其中 α 是阿克曼函数的反函数。
5. 完整代码示例
以下是一个完整的 Java 实现，包含判断连通性的辅助方法：
public 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] = 0;
}
}
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] += 1;
}
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
int n = 10;
UnionFind uf = new UnionFind(n);
uf.union(1, 2);
uf.union(2, 5);
System.out.println("Is 1 and 5 connected? " + uf.isConnected(1, 5)); // true
}
}
6. 应用场景
- 图的连通性：判断图中是否存在环，或两点是否连通（如 Kruskal 算法求最小生成树）。
- 社交网络分析：判断用户是否属于同一圈子。
- 动态连通性问题：频繁更新连通状态的场景。
7. 时间复杂度
- 初始化：O(n)
- 查找/合并：均摊 O(α(n))，几乎为常数时间。
二、例题实战
例题一：水位上升的泳池中游泳
题目描述： 在一个 n x n 的整数矩阵 grid 中，grid[i][j] 表示位置 (i, j) 的平台高度。时间为 t 时，水位为 t。你可以从平台游向四周相邻平台，前提是水位必须同时淹没这两个平台。求从左上角 (0, 0) 到达右下角 (n-1, n-1) 所需的最少时间。
解题思路： 随着时间推移，水位上升，原本不连通的平台可能变得连通。我们可以利用并查集动态维护平台的连通性。
- 初始化：将矩阵中的每个平台视为独立集合。
- 排序：提取所有平台高度并排序，按高度从小到大处理。
- 动态合并：遍历高度，对于当前高度的平台，检查其四个方向。若相邻平台高度小于等于当前水位，则合并。
- 判断连通：每次合并后检查起点和终点是否连通，若连通则当前高度即为答案。
代码实现：
private int N;
public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int swimInWater(int[][] grid) {
this.N = grid.length;
int len = N * N;
int[] index = new int[len];
// 建立高度到坐标的映射
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
index[grid[i][j]] = getIndex(i, j);
}
}
UnionFind uf = new UnionFind(len);
// 按高度顺序处理
for (int i = 0; i < len; i++) {
int x = index[i] / N;
int y = index[i] % N;
for (int[] d : DIRECTIONS) {
int newX = x + d[0];
int newY = y + d[1];
if (inArea(newX, newY) && grid[newX][newY] <= i) {
uf.union(index[i], getIndex(newX, newY));
}
}
if (uf.isConnected(0, len - 1)) {
return i;
}
}
return -1;
}
private int getIndex(int x, int y) {
return x * N + y;
}
private boolean inArea(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N;
}
class UnionFind {
private int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int root(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]]; // 路径压缩
x = parent[x];
}
return x;
}
public boolean isConnected(int x, int y) {
return root(x) == root(y);
}
public void union(int p, int q) {
if (isConnected(p, q)) return;
parent[root(p)] = root(q);
}
}
例题二：省份数量
题目描述： 给定 n x n 的矩阵 isConnected，isConnected[i][j] = 1 表示城市 i 和 j 直接相连。返回省份的数量（即连通分量的数量）。
解题思路： 将每个城市视为一个元素，遍历邻接矩阵。若 isConnected[i][j] == 1，则将城市 i 和 j 合并。最终统计连通分量的数量。
代码实现：
public int findCircleNum(int[][] isConnected) {
if (isConnected == null || isConnected.length == 0) return 0;
int n = isConnected.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.getCount();
}
class UnionFind {
int[] root;
int[] rank;
int count;
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
count = size;
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1;
}
}
public int find(int x) {
if (x == root[x]) return x;
return root[x] = find(root[x]);
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX] += 1;
}
count--;
}
}
public int getCount() {
return count;
}
}
总结
并查集在处理动态连通性问题时非常高效。掌握路径压缩和按秩合并这两项优化技巧，能让算法性能达到理论最优。在实际开发中，遇到类似图论或分组问题，不妨优先考虑并查集方案。