1.5.13

1.5.13 #

解答 #

官方实现：WeightedQuickUnionPathCompressionUF。

加权 quick-union 中，两个大小相等的树合并可以有效增加高度，同时输入必须保证是根节点以规避路径压缩。

代码 #

WeightedQuickUnionPathCompressionUF.cs 从 WeightedQuickUnionUF.cs 继承，详情参见 1.5.3 的解答。

public class WeightedQuickUnionPathCompressionUf : WeightedQuickUnionUf
{
    /// <summary>
    /// 新建一个大小为 n 的并查集。
    /// </summary>
    /// <param name="n">新建并查集的大小。</param>
    public WeightedQuickUnionPathCompressionUf(int n) : base(n)
    {
        Size = new int[n];

        for (var i = 0; i < n; i++)
        {
            Size[i] = 1;
        }
    }

    /// <summary>
    /// 寻找一个结点所在的连通分量。
    /// </summary>
    /// <param name="p">需要寻找的结点。</param>
    /// <returns>该结点所属的连通分量。</returns>
    public override int Find(int p)
    {
        Validate(p);
        var root = p;
        while (root != Parent[p])
        {
            root = Parent[p];
        }
        while (p != root)
        {
            var newP = Parent[p];
            Parent[p] = root;
            p = newP;
        }
        return root;
    }
}

Main 方法

var uf = new WeightedQuickUnionPathCompressionUf(10);

// 见中文版 P146 或英文版 P229 中加权 quick-union 的最坏输入。
uf.Union(0, 1);
uf.Union(2, 3);
uf.Union(4, 5);
uf.Union(6, 7);
uf.Union(0, 2);
uf.Union(4, 6);
uf.Union(0, 4);

var id = uf.GetParent();
for (var i = 0; i < id.Length; i++)
{
    Console.Write(id[i]);
}

Console.WriteLine();

另请参阅 #

UnionFind 库