1.5.2 #

解答 #

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。

public class QuickUnionUf : Uf
{
    /// <summary>
    /// 数组访问次数的计数器。
    /// </summary>
    /// <value>当前数组访问次数。</value>
    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()
    {
        ArrayVisitCount = 0;
    }

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

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

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

        Parent[rootP] = rootQ;
        ArrayVisitCount++;
        TotalCount--;
    }
}

Main 方法

var input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
var quickUnion = new QuickUnionUf(10);

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

    quickUnion.Union(p, q);
    var parent = quickUnion.GetParent();
    for (var 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 (var i = 0; i < parent.Length; i++)
    {
        if (parent[i] == root && i != root)
        {
            for (var j = 0; j < level; j++)
            {
                Console.Write("    ");
            }

            Console.WriteLine("|---- " + i);
            Dfs(parent, i, level + 1);
        }
    }
}

另请参阅 #

UnionFind 库