1.5.12

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

解答

QuickUnionPathCompression 的官方实现:QuickUnionPathCompressionUF.java
在找到根节点之后,再访问一遍 p 到根节点这条路径上的所有结点,将它们直接和根节点相连。
重写过后的 Find() 方法:

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

由于路径压缩是在 Find() 方法中实现的,
只要输入保证是根节点两两相连即可构造较长的路径。

代码

QuickUnionPathCompressionUF.cs 直接从 QuickUnionUF.cs 继承而来。
关于 QuickUnionUF.cs,参见 1.5.2 的解答。

namespace UnionFind
{
    /// <summary>
    /// 使用路径压缩的 quick-union 并查集。
    /// </summary>
    public class QuickUnionPathCompressionUF : QuickFindUF
    {
        /// <summary>
        /// 新建一个大小为 n 的并查集。
        /// </summary>
        /// <param name="n">新建并查集的大小。</param>
        public QuickUnionPathCompressionUF(int n) : base(n) { }

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

Main 方法

using System;
using UnionFind;

namespace _1._5._12
{
    /*
     * 1.5.12
     * 
     * 使用路径压缩的 quick-union 算法。
     * 根据路径压缩修改 quick-union 算法(请见 1.5.2.3 节),
     * 在 find() 方法中添加一个循环来将从 p 到根节点的路径上的每个触点都连接到根节点。
     * 给出一列输入,使该方法能够产生一条长度为 4 的路径。
     * 注意:该算法的所有操作的均摊成本已知为对数级别。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            var UF = new QuickUnionPathCompressionUF(10);

            // 使用书中提到的最坏情况,0 连 1,1 连 2,2 连 3……
            for (int i = 0; i < 4; ++i)
            {
                UF.Union(i, i + 1);
            }

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

另请参阅

UnionFind 库

上一题 下一题