1.5.1

1.5.1 #

解答 #

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。

/// <summary>
/// 用 QuickFind 算法实现的并查集。
/// </summary>
public class QuickFindUf : Uf
{
    /// <summary>
    /// 记录数组访问次数的计数器。
    /// </summary>
    /// <value>记录数组访问的计数器。</value>
    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()
    {
        ArrayVisitCount = 0;
    }
        
    /// <summary>
    /// 寻找 p 所在的连通分量。
    /// </summary>
    /// <param name="p">需要寻找的结点。</param>
    /// <returns><paramref name="p"/> 所在的连通分量。</returns>
    public override int Find(int p)
    {
        Validate(p);
        ArrayVisitCount++;
        return Parent[p];
    }

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

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

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

        for (var i = 0; i < Parent.Length; i++)
        {
            if (Parent[i] == pId)
            {
                Parent[i] = qId;
                ArrayVisitCount++;
            }
        }

        ArrayVisitCount += Parent.Length;
        TotalCount--;
    }

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

另请参阅 #

UnionFind 库