1.5.1

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

解答

quick-find 的官方实现:QuickFindUF.java
只要实现相应并查集,然后输入内容即可。
增加一个记录访问数组次数的类成员变量,在每次访问数组的语句执行后自增即可。
样例输出:

1 2 3 4 5 6 7 8 0 数组访问:13
1 2 4 4 5 6 7 8 0 数组访问:13
1 2 4 4 8 6 7 8 0 数组访问:13
1 2 4 4 8 6 2 8 0 数组访问:13
1 1 4 4 8 6 1 8 0 数组访问:14
1 1 4 4 1 6 1 1 0 数组访问:14
1 1 4 4 1 6 1 1 4 数组访问:14
1 1 1 1 1 6 1 1 1 数组访问:16

代码

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

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

        /// <summary>
        /// 新建一个使用 quick-find 实现的并查集。
        /// </summary>
        /// <param name="n">并查集的大小。</param>
        public QuickFindUF(int n) : base(n) { }

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

        /// <summary>
        /// 寻找 p 所在的连通分量。
        /// </summary>
        /// <param name="p">需要寻找的结点。</param>
        /// <returns>返回 p 所在的连通分量。</returns>
        public override int Find(int p)
        {
            Validate(p);
            this.ArrayVisitCount++;
            return this.parent[p];
        }

        /// <summary>
        /// 判断两个结点是否属于同一个连通分量。
        /// </summary>
        /// <param name="p">需要判断的结点。</param>
        /// <param name="q">需要判断的另一个结点。</param>
        /// <returns>如果属于同一个连通分量则返回 true,否则返回 false。</returns>
        public override bool IsConnected(int p, int q)
        {
            Validate(p);
            Validate(q);
            this.ArrayVisitCount += 2;
            return this.parent[p] == this.parent[q];
        }

        /// <summary>
        /// 将两个结点所在的连通分量合并。
        /// </summary>
        /// <param name="p">需要合并的结点。</param>
        /// <param name="q">需要合并的另一个结点。</param>
        public override void Union(int p, int q)
        {
            Validate(p);
            Validate(q);
            int pID = this.parent[p];
            int qID = this.parent[q];
            this.ArrayVisitCount += 2;

            // 如果两个结点同属于一个连通分量,那么什么也不做。
            if (pID == qID)
            {
                return;
            }

            for (int i = 0; i < this.parent.Length; ++i)
            {
                if (this.parent[i] == pID)
                {
                    this.parent[i] = qID;
                    this.ArrayVisitCount++;
                }
            }

            this.ArrayVisitCount += this.parent.Length;
            this.count--;
            return;
        }

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

另请参阅

UnionFind 库

上一题 下一题