C#并查集(union-find)算法详解

并查集是一种用于维护并查集的一种树型数据结构。用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

每个集合的代表元（元素）用它的祖先来表示。并查集数据结构即为维护一个集合的信息。

并查集可以解决一些经典的连通性问题，如无向图连通性问题、最小生成树问题等。

下面我们来讲解一下如何使用C#实现并查集算法，并且提供两个示例作为说明。

基本思路

并查集的基本思路是通过路径压缩和按秩合并两种优化方式，维护一个元素向其代表元的映射，使得任意时刻每个元素所在的集合都可以通过其代表元唯一确定。

具体来说，就是维护一个数组 parent，其中 parent[i] 表示元素 i 的直接父节点。如果 i 是集合 S 的代表元，那么 parent[i] 就是指向 S 中某个元素 j 的指针，且 j 就是 S 中的一个代表元，即 j = find(i);。

合并操作合并两个集合 S1 和 S2 只需要将 S1 的代表元合并到 S2 的代表元下面即可，这样，仍然可以通过每个元素的代表元唯一确定其所属的集合。

C#代码实现

下面给出C#的实现代码：

public class UnionFindSet
{
    int[] parent;
    int[] rank;

    public UnionFindSet(int n)
    {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);
        if (rootX != rootY)
        {
            if (rank[rootX] < rank[rootY])
            {
                parent[rootX] = rootY;
            }
            else if (rank[rootX] > rank[rootY])
            {
                parent[rootY] = rootX;
            }
            else
            {
                parent[rootY] = rootX;
                ++rank[rootX];
            }
        }
    }

    public int Find(int x)
    {
        if (x != parent[x])
        {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
}

示例说明

示例1：判断图是否联通

给定一个无向图，求该图是否连通。

我们可以依次加入图中的每一条边，判断每条边的两端点是否已经在同一集合中。如果在一集合中，表明加上这条边会与原来的边构成环，因此该边没必要加入。反之，该边可以加入，并将两端点并入同一集合中。

下面是示例代码：

public bool IsConnected(int[][] edges)
{
    int n = edges.Length;
    UnionFindSet ufset = new UnionFindSet(n);

    for(int i = 0; i < n; i++)
    {
        int x = edges[i][0];
        int y = edges[i][1];

        if(ufset.Find(x) != ufset.Find(y))
        {
            ufset.Union(x, y);
        }
    }

    int first = ufset.Find(0);
    for(int i = 1; i < n; i++)
    {
        if(ufset.Find(i) != first)
        {
            return false;
        }
    }

    return true;
}

示例2：计算岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛屿是由相邻的 '1' （代表陆地）组成的集合，每个位置只有上下左右相邻的另一个位置也是陆地时，才认为这两个位置属于同一个岛屿。

下面是示例代码：

public int NumIslands(char[][] grid)
{
    int rows = grid.Length;
    int cols = grid[0].Length;

    UnionFindSet ufset = new UnionFindSet(rows * cols);
    int num0s = 0;

    for(int r = 0; r < rows; r++)
    {
        for(int c = 0; c < cols; c++)
        {
            if(grid[r][c] == '0')
            {
                num0s++;
                continue;
            }
            if(r > 0 && grid[r - 1][c] == '1')
            {
                ufset.Union(r * cols + c, (r - 1) * cols + c);
            }
            if(c > 0 && grid[r][c - 1] == '1')
            {
                ufset.Union(r * cols + c, r * cols + c - 1);
            }
        }
    }

    int isls = rows * cols - num0s;
    return isls - ufset.GetNumOfSets();
}

在示例2中，我们首先遍历整个网格，对每个网格的相邻位置进行并集操作。最后，网格的总个数减去“0”字符中个数，就是岛屿的数量。