一、什么是并查集？

并查集（Union-Find），也称为不相交集合数据结构（Disjoint-Set Data Structure），是一种用于处理元素分组和集合合并与查询的高效数据结构。它主要支持两种操作：

• 合并（Union）：将两个元素所在的集合合并为一个集合。
• 查找（Find）：查询某个元素属于哪个集合（通常返回该集合的“代表元”）。

并查集在解决连通性、动态连通、图论中的连通分量等问题上有着广泛的应用，其近乎常数时间的操作复杂度使其成为算法竞赛和工程实践中的利器。

二、核心思想与数据结构

并查集的核心思想是使用树形结构来表示集合。每个集合用一棵树来表示，树的根节点（代表元）作为该集合的标识。初始时，每个元素自成一个集合（即自己是自己的根）。

数据结构通常使用一个父节点数组（parent）来实现：

• parent[i] 表示元素 i 的父节点。
• 如果 parent[i] == i，则 i 是所在集合的根节点（代表元）。

三、基础操作与优化

1. 初始化

初始化时，每个元素都是独立的集合，即自己是自己的根。

class UnionFind {
    private int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 每个元素自成一派
        }
    }
}

2. 查找（Find）

查找元素所在集合的根节点（代表元）。朴素实现是沿着父节点一直向上找。

public int find(int x) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

路径压缩优化：在查找过程中，将沿途所有节点的父节点直接指向根节点，使树的高度降低，极大提升后续查找效率。

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归压缩
    }
    return parent[x];
}

3. 合并（Union）

将两个元素所在的集合合并。朴素实现是将一个集合的根节点指向另一个集合的根节点。

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY; // 将 rootX 的根指向 rootY
    }
}

按秩合并优化：为了保持树的平衡，避免退化成链，我们记录每个树的“秩”（如高度或大小），总是将秩较小的树合并到秩较大的树上。

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;
        }
    }
    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
            }
        }
    }
}

四、完整 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] = 1;
        }
    }

    // 查找（带路径压缩）
    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]++;
            }
        }
    }

    // 判断两个元素是否连通
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

五、典型应用场景

1. 判断图中节点是否连通

给定一个无向图，动态添加边，实时判断两个节点是否连通。

2. 朋友圈问题（LeetCode 547）

有 n 个人，如果 a 和 b 是朋友，b 和 c 是朋友，则 a 和 c 也是朋友。求朋友圈的个数。

3. 岛屿数量（LeetCode 200）

可以用并查集替代 DFS/BFS 来统计网格中“1”构成的连通块数量。

4. 最小生成树（Kruskal 算法）

Kruskal 算法中，并查集用于判断加入一条边后是否会形成环。

六、复杂度分析

• 空间复杂度：O(n)，用于存储 parent 和 rank 数组。
• 时间复杂度（均摊）：
  • 仅使用路径压缩或按秩合并：O(log n)。
  • 同时使用路径压缩和按秩合并：O(α(n))，其中 α(n) 是反阿克曼函数，增长极其缓慢，可以近似看作常数时间。

七、总结

并查集是一种简洁而强大的数据结构，其核心在于路径压缩和按秩合并两种优化，使得合并与查找操作近乎常数时间。掌握并查集，能够高效解决许多与连通性、分组相关的算法问题。

建议读者动手实现一遍基础版本，再逐步加上优化，并通过 LeetCode 相关题目（如 547、200、684、721）进行巩固练习。