并查集：集合合并与动态连通性
介绍基于 HashMap 和数组的并查集实现，并应用于朋友圈和岛屿数量问题。
1. 并查集
并查集（Disjoint Set Union, DSU）是一种用于管理元素所属集合的高效数据结构。它主要处理“动态连通性”问题，能够以极高的效率完成两个核心操作：
- Find（查询）：确定某个元素属于哪个集合（即寻找该集合的代表元素/根节点）。
- Union（合并）：将两个不相交的集合合并为一个集合。
1. 1 通用泛型实现：基于 HashMap 的并查集
在处理非数字类型（如字符串标签、对象引用）或离散型数据时，基于 HashMap 的实现提供了极大的灵活性。
1.1.1 核心设计与优化
该实现使用两个哈希表：
fatherMap：存储每个节点指向的父节点。Key 为当前节点，Value 为父节点。sizeMap：存储每个代表节点（根节点）所在集合的大小。
优化策略：
- 路径压缩 (Path Compression)：在
findFather过程中，利用栈（Stack）记录沿途经过的所有节点。一旦找到根节点，将路径上所有节点的父节点直接指向根节点。这使得树结构变得极其扁平，大幅加速后续查询。 - 按秩合并 (Union by Size)：在
union操作时，总是将“小集合”挂载到“大集合”下面，防止树的高度增长过快。
1.1.2 代码实现
java
public class DSUHashMap {
public static class DSU<V> {
HashMap<V, V> father;
HashMap<V, Integer> size;
public DSU() {
father = new HashMap<>();
size = new HashMap<>();
}
public DSU(List<V> vals) {
father = new HashMap<>();
size = new HashMap<>();
for (V cur : vals) {
father.put(cur, cur);
size.put(cur, 1);
}
}
public V findFather(V cur) {
Stack<V> path = new Stack<>();
while(cur != father.get(cur)) {
path.push(cur);
cur = father.get(cur);
}
while (!path.isEmpty()) {
V pop = path.pop();
father.put(pop, cur);
}
return cur;
}
public void union (V a, V b) {
V aFather = findFather(a);
V bFather = findFather(b);
if (aFather != bFather) {
int sizeA = size.get(aFather);
int sizeB = size.get(bFather);
if (sizeA <= sizeB) {
father.put(aFather, bFather);
size.put(bFather, sizeA + sizeB);
size.remove(aFather);
} else {
father.put(bFather, aFather);
size.put(aFather, sizeA + sizeB);
size.remove(bFather);
}
}
}
public boolean isSameSet(V a, V b) {
return findFather(a) == findFather(b);
}
}
}
1.2 高性能优化：基于数组的并查集
当元素是连续的整数（0 到 N-1）时，使用数组代替哈希表可以显著降低常数项时间开销，并减少内存占用。这是算法竞赛和高频计算场景中的首选方案。注意，这只适用于整数类型
1.2.1 核心设计与优化
- 数组结构：使用
father数组存储父索引，size数组存储集合大小。 - 手动模拟栈：为了进一步极致优化，在
getFather（即查询操作）中，代码没有使用 Java 内置的 Stack 类，而是使用一个名为path的整型数组和一个指针pI来手动模拟栈的行为。这种做法避免了对象创建和自动装箱拆箱的开销。
1.2.2 代码实现
java
public class DSUInteger {
public class DSU {
public static final int lim = 100000;
public static int[] father = new int[lim];
public static int[] size = new int[lim];
public static int[] path = new int[lim];
public static void init(int n) {
for (int i = 0; i < n; i++) {
father[i] = i;
size[i] = 1;
}
}
public static int getFather(int cur) {
int pI = 0;
while (cur != father[cur]) {
path[pI++] = cur;
cur = father[cur];
}
for (int i = pI - 1; i >= 0; i--) {
father[path[i]] = cur;
}
return cur;
}
public static void union(int a, int b) {
int aFather = getFather(a);
int bFather = getFather(b);
if (aFather != bFather) {
int aSize = size[aFather];
int bSize = size[bFather];
if (aSize <= bSize) {
father[aFather] = bFather;
size[bFather] = size[aFather] + size[bFather];
size[aFather] = 0;
} else {
father[bFather] = aFather;
size[aFather] = size[aFather] + size[bFather];
size[bFather] = 0;
}
}
}
public static boolean isSameSet(int a, int b) {
return getFather(a) == getFather(b);
}
}
}
3. 朋友圈问题
该问题（对应 LeetCode 547 - 省份数量）是并查集的典型应用场景。给定一个 N*N 的邻接矩阵，要求计算独立的连通分量个数。
3.1 解题思路
- 初始化：初始化并查集，初始集合数量
setNum等于城市总数 N。 - 对称性遍历：由于无向图的邻接矩阵是对称的（即
i与j连通等价于j与i连通），只需要遍历矩阵的上半部分（即j > i的部分）。 - 合并逻辑：如果
isConnected[i][j] == 1，说明两城市连通，执行union(i, j)。 - 结果：在
union操作中，每成功合并两个不同的集合，总集合数setNum减 1。最终返回dsu.getSetNum()。
3.2 代码实现
java
public class FriendCircleProblem {
public int findCircleNum(int[][] isConnected) {
if (isConnected == null || isConnected.length == 0) {
return 0;
}
DSU dsu = new DSU(isConnected.length);
for (int i = 0; i < isConnected.length; i++) {
for (int j = i + 1; j < isConnected[0].length; j++) {
if (isConnected[i][j] == 1) {
dsu.union(i, j);
}
}
}
return dsu.getSetNum();
}
public class DSU {
public int[] father;
public int[] size;
public int[] path;
public int setNum;
public DSU(int n) {
father = new int[n];
size = new int[n];
path = new int[n];
setNum = n;
for (int i = 0; i < n; i++) {
father[i] = i;
size[i] = 1;
}
}
public int findFather(int cur) {
int pI = 0;
while (cur != father[cur]) {
path[pI++] = cur;
cur = father[cur];
}
pI--;
while (pI >= 0) {
father[path[pI--]] = cur;
}
return cur;
}
public boolean isSameSet(int a, int b) {
return findFather(a) == findFather(b);
}
public void union(int a, int b) {
int aFather = findFather(a);
int bFather = findFather(b);
int aSize = size[aFather];
int bSize = size[bFather];
if (aFather != bFather) {
if (aSize <= bSize) {
father[aFather] = bFather;
size[bFather] = aSize + bSize;
size[aFather] = 0;
} else {
father[bFather] = aFather;
size[aFather] = aSize + bSize;
size[bFather] = 0;
}
setNum--;
}
}
public int getSetNum() {
return setNum;
}
}
}
4. 岛问题 I
此问题（LeetCode 200）给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿数量。针对此题，提供了两种不同的解法。
4.1 方法一：DFS 感染法
这是最直观的解法，不需要额外的数据结构。
- 思路：遍历整个二维数组。每当遇到一个 '1' 时，岛屿数量加 1，并立即调用
infect函数。 - 感染过程：
infect函数会将当前位置以及上下左右所有相连的 '1' 全部修改为 '2'。这相当于把当前发现的整座岛屿“抹去”或“标记”，防止后续遍历时重复计算。
java
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int isLands = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
isLands++;
infect(grid, i, j);
}
}
}
return isLands;
}
public void infect(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
if (grid[i][j] == '1') {
grid[i][j] = '2';
infect(grid, i, j - 1);
infect(grid, i, j + 1);
infect(grid, i - 1, j);
infect(grid, i + 1, j);
}
}
4.2 方法二：并查集法
使用并查集解决二维问题，重点在于坐标转换。
- 坐标映射：将二维坐标
(row, col)映射为一维索引index = row * totalCols + col。 - 初始化：初始化 DSU，大小为网格总格子数。
- 遍历与合并：
- 遍历网格，每遇到 '1'，先假设它是一个独立的岛屿，
setNum增加。 - 为了不重复判断，遍历时只需要尝试与左边
(i, j-1)和上边(i-1, j)的陆地进行合并即可。如果合并成功，setNum自动减少。
- 遍历网格，每遇到 '1'，先假设它是一个独立的岛屿，
java
public int numIslands2(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
DSU dsu = new DSU(rows * cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
dsu.setNum++;
int curId = i * cols + j;
if (j - 1 >= 0 && grid[i][j - 1] == '1') {
dsu.union(curId, curId - 1);
}
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
dsu.union(curId, curId - cols);
}
}
}
}
return dsu.getSetNum();
}
public class DSU {
public int[] father;
public int[] size;
public int setNum;
public DSU(int n) {
father = new int[n];
size = new int[n];
setNum = 0;
for (int i = 0; i < n; i++) {
father[i] = i;
size[i] = 1;
}
}
public int findFather(int cur) {
if (cur != father[cur]) {
father[cur] = findFather(father[cur]);
}
return father[cur];
}
public void union(int a, int b) {
int aFather = findFather(a);
int bFather = findFather(b);
if (aFather != bFather) {
if (size[aFather] >= size[bFather]) {
father[bFather] = aFather;
size[aFather] += size[bFather];
} else {
father[aFather] = bFather;
size[bFather] += size[aFather];
}
setNum--;
}
}
public int getSetNum() {
return setNum;
}
}
5. 岛问题 II
此问题（LeetCode 305）是岛屿问题的进阶版。陆地不是一次性给出的，而是根据 positions 列表一个接一个动态“填海造陆”。每次操作后，都需要返回当前的岛屿数量。
5.1 动态处理逻辑
由于陆地是动态生成的，并查集是处理此类“动态连通性”的最佳选择。
- 状态初始化：创建一个
parent数组，全部初始化为 -1，表示所有位置最初都是“水”。 - 处理新陆地：
- 遍历
positions，计算当前位置的一维index。 - 去重：如果
parent[index]不为 -1，说明该位置已经是陆地，无需操作，直接记录当前计数。 - 初始假设：将新位置标记为陆地 (
parent[index] = index)，并假设它是一个新的独立岛屿，岛屿总数count加 1。
- 遍历
- 四周探测与合并：
- 检查该位置的上、下、左、右四个邻居。
- 连通判断：如果邻居在网格范围内且
parent不为 -1（即邻居也是陆地），则查找两者的根节点。 - 如果根节点不同，说明两块岛屿连成了一片，执行合并操作，并将岛屿总数
count减 1。
5.2 代码实现
java
public class DSUIslandProblem2 {
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
int[] parent = new int[m * n];
Arrays.fill(parent, -1);
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int count = 0;
for (int[] pos : positions) {
int r = pos[0];
int c = pos[1];
int index = r * n + c;
if (parent[index] != -1) {
result.add(count);
continue;
}
parent[index] = index;
count++;
for (int[] dir : dirs) {
int nr = r + dir[0];
int nc = c + dir[1];
int neighborIndex = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && parent[neighborIndex] != -1) {
int rootA = find(parent, index);
int rootB = find(parent, neighborIndex);
if (rootA != rootB) {
parent[rootA] = rootB;
count--;
}
}
}
result.add(count);
}
return result;
}
private int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
}