高效处理集合合并与查询：C#并查集（Union-Find）详解（附路径压缩优化技巧）

基础版 C# 并查集实现

下面是一个没有优化的基础版本：

public 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 Find(int x)    {        while (parent[x] != x)        {            x = parent[x];        }        return x;    }    // 合并两个集合    public void Union(int x, int y)    {        int rootX = Find(x);        int rootY = Find(y);        if (rootX != rootY)        {            parent[rootX] = rootY;        }    }}

这个实现虽然正确，但效率不高。例如，当树退化成链表时，Find 操作的时间复杂度会达到 O(n)。这时候就需要引入路径压缩来优化。

路径压缩：让查找更快！

路径压缩的核心思想是：在执行 Find 操作时，将路径上的所有节点直接连接到根节点。这样下次再查找这些节点时，就能一步到位。

例如，原本查找 4 的根需要经过 4 → 3 → 2 → 1，路径压缩后，4、3、2 都直接指向 1，大大减少了后续查找时间。

带路径压缩的 C# 并查集实现

我们只需修改 Find 方法，采用递归或迭代方式实现路径压缩。以下是递归写法（更简洁）：

public class UnionFindWithPathCompression{    private int[] parent;    public UnionFindWithPathCompression(int n)    {        parent = new int[n];        for (int i = 0; i < n; i++)        {            parent[i] = i;        }    }    // 带路径压缩的 Find    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)        {            parent[rootX] = rootY;        }    }}

通过路径压缩，Find 操作的平均时间复杂度接近 O(α(n))，其中 α 是反阿克曼函数，增长极其缓慢——对于任何实际应用来说，几乎可以视为常数时间！

应用场景举例

并查集广泛应用于以下场景：

• 判断图中两点是否连通（如网络连接检测）
• Kruskal 最小生成树算法中的环检测
• 社交网络中的“共同好友”或“群组合并”
• 岛屿数量问题（LeetCode 经典题）

总结

通过本文，你已经掌握了 C# 并查集 的基本实现和 路径压缩 优化技巧。并查集虽然结构简单，但在处理动态连通性问题时非常高效。结合路径压缩（有时还会配合“按秩合并”优化），它能以近乎常数的时间完成操作。

记住这些关键词：**C#并查集**、**路径压缩**、**Union-Find算法**、**C#数据结构**——它们不仅是面试高频考点，也是解决实际工程问题的利器！

动手试试吧！用上面的代码解决一道 LeetCode 的“省份数量”或“岛屿数量”题目，你会对并查集有更深的理解。