1.5.3

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

解答

加权 quick-union 的官方实现:WeightedQuickUnionUF.java
样例输出:

1 2 3 4 5 6 7 8 9 数组访问:3
1 2 3 3 5 6 7 8 9 数组访问:3
1 2 3 3 5 6 7 5 9 数组访问:3
1 7 3 3 5 6 7 5 9 数组访问:3
7 7 3 3 5 6 7 5 9 数组访问:5
7 7 3 3 7 6 7 5 9 数组访问:3
7 7 9 3 7 6 7 5 9 数组访问:5
7 7 9 3 7 6 7 5 7 数组访问:9

代码

WeightedQuickUnionUF.cs,这个类继承了 QuickUnion.cs,重新实现了 Union() 和 Find() 等方法。

关于 QuickUnion.cs 可以参见 1.5.2 的代码部分。

namespace UnionFind
{
    /// <summary>
    /// 使用加权 quick-union 算法的并查集。
    /// </summary>
    public class WeightedQuickUnionUF : QuickUnionUF
    {
        protected int[] size; // 记录各个树的大小。

        public int ArrayParentVisitCount { get; private set; } // 记录 parent 数组的访问次数。
        public int ArraySizeVisitCount { get; private set; } //记录 size 数组的访问次数。

        /// <summary>
        /// 建立使用加权 quick-union 的并查集。
        /// </summary>
        /// <param name="n">并查集的大小。</param>
        public WeightedQuickUnionUF(int n) : base(n)
        {
            this.size = new int[n];
            for (int i = 0; i < n; ++i)
            {
                this.size[i] = 1;
            }
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 清零数组访问计数。
        /// </summary>
        public override void ResetArrayCount()
        {
            this.ArrayParentVisitCount = 0;
            this.ArraySizeVisitCount = 0;
        }

        /// <summary>
        /// 获取 size 数组。
        /// </summary>
        /// <returns>返回 size 数组。</returns>
        public int[] GetSize()
        {
            return this.size;
        }

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

        /// <summary>
        /// 将两个结点所属的连通分量合并。
        /// </summary>
        /// <param name="p">需要合并的结点。</param>
        /// <param name="q">需要合并的另一个结点。</param>
        public override void Union(int p, int q)
        {
            int rootP = Find(p);
            int rootQ = Find(q);
            if (rootP == rootQ)
            {
                return;
            }

            if (this.size[rootP] < this.size[rootQ])
            {
                this.parent[rootP] = rootQ;
                this.size[rootQ] += this.size[rootP];
            }
            else
            {
                this.parent[rootQ] = rootP;
                this.size[rootP] += this.size[rootQ];
            }
            this.ArrayParentVisitCount++;
            this.ArraySizeVisitCount += 4;
            this.count--;
        }
    }
}

Main 方法

using System;
using UnionFind;

namespace _1._5._3
{
    /*
     * 1.5.3
     * 
     * 使用加权 quick-union 算法(请见算法 1.5)完成练习 1.5.1 。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
            var weightedQuickUnion = new WeightedQuickUnionUF(10);

            foreach (string s in input)
            {
                weightedQuickUnion.ResetArrayCount();
                string[] numbers = s.Split('-');
                int p = int.Parse(numbers[0]);
                int q = int.Parse(numbers[1]);

                weightedQuickUnion.Union(p, q);
                int[] parent = weightedQuickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    Console.Write(parent[i] + " ");
                }
                Console.WriteLine("数组访问:" + weightedQuickUnion.ArrayParentVisitCount);
            }
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题