1.5.13

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

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

代码

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

namespace UnionFind
{
    /// <summary>
    /// 使用路径压缩的加权 quick-union 并查集。
    /// </summary>
    public class WeightedQuickUnionPathCompressionUF : WeightedQuickUnionUF
    {
        /// <summary>
        /// 新建一个大小为 n 的并查集。
        /// </summary>
        /// <param name="n">新建并查集的大小。</param>
        public WeightedQuickUnionPathCompressionUF(int n) : base(n)
        {
            this.size = new int[n];

            for (int i = 0; i < n; ++i)
            {
                this.size[i] = 1;
            }
        }

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

Main 方法

using System;
using UnionFind;

namespace _1._5._13
{
    /*
     * 1.5.13
     * 
     * 使用路径压缩的加权 quick-union 算法。
     * 修改加权 quick-union 算法(算法 1.5),
     * 实现如练习 1.5.12 所述的路径压缩。给出一列输入,
     * 使该方法能产生一棵高度为 4 的树。
     * 注意:该算法的所有操作的均摊成本已知被限制在反 Ackermann 函数的范围之内,
     * 且对于实际应用中可能出现的所有 N 值均小于 5。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            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);

            int[] id = UF.GetParent();
            for (int i = 0; i < id.Length; ++i)
            {
                Console.Write(id[i]);
            }
            Console.WriteLine();
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题