1.5.2

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

解答

quick-union 的官方实现:QuickUnionUF.java
和上题一样的方式,增加一个记录访问数组次数的类成员变量,在每次访问数组的语句执行后自增即可。
程序输出的森林,用缩进表示子树:

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

代码

QuickUnionUF.cs,这个类继承了 UF.cs,重新实现了 Union() 和 Find() 等方法。
关于 UF.cs 可以参见原书中文版 P138 或英文版 P221 的算法 1.5。

namespace UnionFind
{
    /// <summary>
    /// 用 QuickUnion 算法实现的并查集。
    /// </summary>
    public class QuickUnionUF : UF
    {
        public int ArrayVisitCount { get; private set; } //记录数组访问的次数。

        /// <summary>
        /// 建立使用 QuickUnion 的并查集。
        /// </summary>
        /// <param name="n">并查集的大小。</param>
        public QuickUnionUF(int n) : base(n) { }

        /// <summary>
        /// 重置数组访问计数。
        /// </summary>
        public virtual void ResetArrayCount()
        {
            this.ArrayVisitCount = 0;
        }

        /// <summary>
        /// 获得 parent 数组。
        /// </summary>
        /// <returns>返回 parent 数组。</returns>
        public int[] GetParent()
        {
            return this.parent;
        }

        /// <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.ArrayVisitCount += 2;
            }
            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;
            }

            this.parent[rootP] = rootQ;
            this.ArrayVisitCount++;
            this.count--;
        }
    }

}

Main 方法

using System;
using UnionFind;

namespace _1._5._2
{
    /*
     * 1.5.2
     * 
     * 使用 quick-union 算法(请见 1.5.2.3 节代码框)完成练习 1.5.1。
     * 另外,在处理完输入的每对整数之后画出 id[] 数组表示的森林。
     * 
     */
    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 quickUnion = new QuickUnionUF(10);

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

                quickUnion.Union(p, q);
                int[] parent = quickUnion.GetParent();
                for (int i = 0; i < parent.Length; ++i)
                {
                    if (parent[i] == i)
                    {
                        Console.WriteLine("|---- " + i);
                        DFS(parent, i, 1);
                    }
                }
                Console.WriteLine("数组访问:" + quickUnion.ArrayVisitCount);
            }
        }

        static void DFS(int[] parent, int root, int level)
        {
            for (int i = 0; i < parent.Length; ++i)
            {
                if (parent[i] == root && i != root)
                {
                    for (int j = 0; j < level; ++j)
                    {
                        Console.Write("    ");
                    }
                    Console.WriteLine("|---- " + i);
                    DFS(parent, i, level + 1);
                }
            }
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题