并查集
大约 4 分钟
并查集
- OI Wiki: https://oi-wiki.org/ds/dsu/
| 题目 | 难度 | |
|---|---|---|
| 200. 岛屿数量 | 中等 | 推荐 |
| $261. 以图判树 | 中等 | |
| $305. 岛屿数量 II | 困难 | 推荐 |
| $323. 无向图中连通分量的数目 | 中等 | |
| 547. 省份数量 | 中等 | |
| 684. 冗余连接 | 中等 | |
| 685. 冗余连接 II | 困难 | 推荐 |
| 721. 账户合并 | 中等 | 离散化 |
| $737. 句子相似性 II | 中等 | 离散化 |
| 947. 移除最多的同行或同列石头 | 中等 | HashMap 版本并查集 |
| 2334. 元素值大于变化阈值的子数组 | 困难 | 连通分量合并到较小的节点 |
并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：
- 查找（Find）：确定某个元素处于哪个子集；
- 合并（Union）：将两个子集合并成一个集合。
初始化、查找、合并
public class DSU {
// 父节点数组/祖先数组
int[] fa;
// 初始化
public DSU(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
// 查找
int find(int x) {
// 路径压缩
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
// 合并
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
fa[rootQ] = rootP;
}
}
时间复杂度
| 优化 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 无优化 | O(logn) | O(n) |
| 路径压缩 | O(α(n)) | O(logn) |
| 按秩合并 | O(logn) | O(logn) |
| 路径压缩 + 按秩合并 | O(α(n)) | O(α(n)) |
这里 α 表示阿克曼函数的反函数，在宇宙可观测的 n 内（例如宇宙中包含的粒子总数），α(n) 不会超过 5。
200. 岛屿数量
连通分量 逐渐合并减少。
public class Solution200 {
public int numIslands(char[][] grid) {
int M = grid.length;
int N = grid[0].length;
// 岛屿数目
int cnt = 0;
for (char[] chars : grid) {
for (char aChar : chars) {
if (aChar == '1') {
cnt++;
}
}
}
DSU dsu = new DSU(M * N);
dsu.sz = cnt;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == '1') {
int p = i * N + j;
// up
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
dsu.union(p, p - N);
}
// down
if (i + 1 < M && grid[i + 1][j] == '1') {
dsu.union(p, p + N);
}
// left
if (j - 1 >= 0 && grid[i][j - 1] == '1') {
dsu.union(p, p - 1);
}
// right
if (j + 1 < N && grid[i][j + 1] == '1') {
dsu.union(p, p + 1);
}
}
}
}
return dsu.sz;
}
private static class DSU {
int[] fa;
int sz;
public DSU(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
fa[rootQ] = rootP;
sz--;
}
}
}
$305. 岛屿数量 II
连通分量 要从 0 开始增加。
import java.util.ArrayList;
import java.util.List;
public class Solution305 {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
int[][] grid = new int[m][n];
List<Integer> resList = new ArrayList<>();
DSU dsu = new DSU(m * n);
for (int[] position : positions) {
int i = position[0];
int j = position[1];
if (grid[i][j] == 0) {
grid[i][j] = 1;
// 增加一个岛屿
dsu.sz++;
int p = position[0] * n + position[1];
// up
if (i - 1 >= 0 && grid[i - 1][j] == 1) {
dsu.union(p, p - n);
}
// down
if (i + 1 < m && grid[i + 1][j] == 1) {
dsu.union(p, p + n);
}
// left
if (j - 1 >= 0 && grid[i][j - 1] == 1) {
dsu.union(p, p - 1);
}
// right
if (j + 1 < n && grid[i][j + 1] == 1) {
dsu.union(p, p + 1);
}
}
resList.add(dsu.sz);
}
return resList;
}
private static class DSU {
int[] fa;
int sz;
public DSU(int n) {
fa = new int[n];
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
fa[rootQ] = rootP;
sz--;
}
}
}
947. 移除最多的同行或同列石头
import java.util.HashMap;
import java.util.Map;
public class Solution947 {
public int removeStones(int[][] stones) {
DSU dsu = new DSU();
for (int[] stone : stones) {
// 并查集里如何区分横纵坐标 下面这三种写法任选其一
// dsu.union(~stone[0], stone[1]);
// dsu.union(stone[0] - 10001, stone[1]);
dsu.union(stone[0] + 10001, stone[1]);
}
return stones.length - dsu.sz;
}
private static class DSU {
Map<Integer, Integer> faMap;
int sz;
public DSU() {
faMap = new HashMap<>();
}
int find(int x) {
if (!faMap.containsKey(x)) {
faMap.put(x, x);
sz++;
}
if (x != faMap.get(x)) {
faMap.put(x, find(faMap.get(x)));
}
return faMap.get(x);
}
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
faMap.put(rootQ, rootP);
sz--;
}
}
}
2334. 元素值大于变化阈值的子数组
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution2334 {
public int validSubarraySize(int[] nums, int threshold) {
int n = nums.length;
Integer[] ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(ids, (o1, o2) -> Integer.compare(nums[o2], nums[o1]));
DSU dsu = new DSU(n);
for (int i : ids) {
int faI = dsu.find(i);
int faJ = dsu.find(i + 1);
// 贪心，优先 union 较大的数
dsu.union(faI, faJ);
int k = dsu.sz[faI] - 1;
if (nums[i] > threshold / k) {
return k;
}
}
return -1;
}
private static class DSU {
int[] fa;
int[] sz;
public DSU(int n) {
int N = n + 1;
fa = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
}
void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 合并到较小的节点
if (rootP < rootQ) {
fa[rootQ] = rootP;
sz[rootP] += sz[rootQ];
} else {
fa[rootP] = rootQ;
sz[rootQ] += sz[rootP];
}
}
}
}
参考链接
（全文完）