并查集实战：用Union-Find高效解决LeetCode朋友圈与岛屿问题

在算法面试中，并查集（Union-Find）是一种常被忽视却威力巨大的数据结构。它能在近乎常数时间内完成集合合并与查询操作，特别适合处理动态连通性问题。本文将以LeetCode经典题目547号「朋友圈」和200号「岛屿数量」为例，手把手教你如何识别并查集适用场景，并给出可直接套用的Python/Java代码模板。

1. 并查集核心原理与优化策略

并查集本质上是通过森林结构维护动态连通关系的工具。其核心操作包含：

• Find：查找元素所属集合（即根节点）
• Union：合并两个元素所在的集合
• Connected：判断两个元素是否连通

1.1 三种实现方式对比

实现方式	Find时间复杂度	Union时间复杂度	空间复杂度	适用场景
Quick-Find	O(1)	O(N)	O(N)	查询频繁但合并少的场景
Quick-Union	O(tree height)	O(tree height)	O(N)	一般情况
加权Quick-Union	O(logN)	O(logN)	O(N)	大规模数据合并

# 加权Quick-Union Python实现
class UnionFind:
    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.rank = [1] * size
    
    def find(self, x):
        while x != self.root[x]:
            x = self.root[x]
        return x
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

提示：路径压缩优化可以在find操作中将节点直接链接到根节点，进一步降低树高。只需在find方法中添加一行：self.root[x] = self.root[self.root[x]]

2. LeetCode 547：朋友圈问题实战

题目描述：一个班级中有N个学生，给出M×M的矩阵表示朋友关系（1表示直接朋友），求朋友圈总数。

2.1 问题转化技巧

将每个学生视为节点，朋友关系视为边。朋友圈数量等于连通分量的数量：

1. 初始化并查集，每个学生独立成集合
2. 遍历矩阵，对每个为1的关系执行union操作
3. 最终统计根节点数量即为答案

// Java解法
class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (M[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.count();
    }
    
    class UnionFind {
        private int[] parent;
        private int count;
        
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            count = n;
        }
        
        public int find(int p) {
            while (p != parent[p]) {
                parent[p] = parent[parent[p]];  // 路径压缩
                p = parent[p];
            }
            return p;
        }
        
        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            parent[rootP] = rootQ;
            count--;
        }
        
        public int count() {
            return count;
        }
    }
}

2.2 复杂度分析

• 时间复杂度：O(N²α(N))，其中α为反阿克曼函数，通常认为接近O(1)
• 空间复杂度：O(N)用于存储父节点数组

3. LeetCode 200：岛屿数量问题

题目描述：给定由'1'（陆地）和'0'（水）组成的二维网格，计算岛屿数量（被水包围的陆地连通区域）。

3.1 并查集解法步骤

1. 初始化：将每个'1'视为独立岛屿，'0'不处理
2. 遍历网格，对每个'1'检查其右侧和下侧相邻格子
3. 如果相邻也是'1'则执行union操作
4. 最终统计根节点数量即为岛屿数

# Python解法
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        uf = UnionFind(rows * cols)
        directions = [(1,0), (0,1)]  # 只需检查右和下
        
        count = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    count += 1
                    idx = i * cols + j
                    for di, dj in directions:
                        ni, nj = i + di, j + dj
                        if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
                            nidx = ni * cols + nj
                            if not uf.connected(idx, nidx):
                                uf.union(idx, nidx)
                                count -= 1
        return count

3.2 优化技巧

• 虚拟节点法：为所有水域创建公共父节点，减少union操作
• 按秩合并：在union时总是将小树合并到大树下，保持树平衡
• 一维映射：将二维坐标线性化为一维索引，简化处理

4. 并查集解题模板与调试技巧

4.1 通用解题模板

1. 识别问题类型：涉及动态连通性、分组或聚类的问题
2. 设计节点与边：确定什么作为节点，什么关系触发union
3. 初始化结构：根据数据规模创建并查集实例
4. 处理边界条件：如空输入、单个元素等特殊情况
5. 统计结果：通过count或遍历计算连通分量

4.2 常见错误排查

• 数组越界：确保find操作中的索引有效
• 初始化错误：父数组应初始化为各自索引
• 重复合并：union前应先检查是否已连通
• 方向遗漏：在网格问题中确保检查所有必要方向

// 调试示例：打印并查集状态
void debugPrint(UnionFind uf, int n) {
    System.out.print("Parent: ");
    for (int i = 0; i < n; i++) {
        System.out.print(uf.find(i) + " ");
    }
    System.out.println();
}

掌握并查集不仅能解决特定算法题，更能培养将实际问题抽象为连通性问题的思维能力。建议在理解基础实现后，尝试解决LeetCode 128（最长连续序列）、130（被围绕的区域）等扩展题目来巩固这一技术。