并查集

public class UnionFind
{
    // i的根节点时root[i]
    private int[] root;

    public UnionFind(int size)
    {
        root = new int[size];
        for(int i = 0; i < size; i++)
        {
            root[i] = i;
        }
    }

    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);
        if(rootX != rootY)
            root[rootX] = rootY;
    }

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

优化：

public class UnionFind
{
    // i的根节点时root[i]
    private int[] root;
    private int[] rank;

    public UnionFind(int size)
    {
        root = new int[size];
        for(int i = 0; i < size; i++)
        {
            root[i] = i;
            rank[i] = 0;
        }
    }

    public void Union(int x, int y)
    {
        int rootX = Find(x);
        int rootY = Find(y);
        if(rootX != rootY)
            root[rootX] = rootY;
    }

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

    public int QuickFind(int x)
    {
        if(x == root[x])
            return root[x];
        root[x] = Find(root[x]);
        return root[x];
    }
    // 比较两个树的高,矮的连到高的上面
    public void QuickUnion(int x, int y)
    {
        int rootX = QuickFind(x);
        int rootY = QuickFind(y);
        if(rootX != rootY)
        {
            if(rank[rootX] > rank[rootY])
            {
                root[rootY] = rootX;
            }
            else if(rank[rootX] < rank[rootY])
            {
                root[rootX] = rootY;
            }
            else
            {
                root[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}