1.5.3 #
解答 #
加权 quick-union 的官方实现：WeightedQuickUnionUF.java。
样例输出：
1 2 3 4 5 6 7 8 9 数组访问：3
1 2 3 3 5 6 7 8 9 数组访问：3
1 2 3 3 5 6 7 5 9 数组访问：3
1 7 3 3 5 6 7 5 9 数组访问：3
7 7 3 3 5 6 7 5 9 数组访问：5
7 7 3 3 7 6 7 5 9 数组访问：3
7 7 9 3 7 6 7 5 9 数组访问：5
7 7 9 3 7 6 7 5 7 数组访问：9
代码 #
WeightedQuickUnionUF.cs，这个类继承了 QuickUnion.cs，重新实现了 Union() 和 Find() 等方法。
关于 QuickUnion.cs 可以参见 1.5.2 的代码部分。
public class WeightedQuickUnionUf : QuickUnionUf
{
/// <summary>
/// 记录各个树大小的数组。
/// </summary>
/// <value>记录各个树大小的数组。</value>
protected int[] Size;
/// <summary>
/// 记录 parent 数组的访问次数的计数器。
/// </summary>
/// <value>parent 数组的访问次数。</value>
public int ArrayParentVisitCount { get; private set; }
/// <summary>
/// 记录 size 数组的访问次数的计数器。
/// </summary>
/// <value>size 数组的访问次数。</value>
public int ArraySizeVisitCount { get; private set; }
/// <summary>
/// 建立使用加权 quick-union 的并查集。
/// </summary>
/// <param name="n">并查集的大小。</param>
public WeightedQuickUnionUf(int n) : base(n)
{
Size = new int[n];
for (var i = 0; i < n; i++)
{
Size[i] = 1;
}
ArrayParentVisitCount = 0;
ArraySizeVisitCount = 0;
}
/// <summary>
/// 清零数组访问计数。
/// </summary>
public override void ResetArrayCount()
{
ArrayParentVisitCount = 0;
ArraySizeVisitCount = 0;
}
/// <summary>
/// 获取 size 数组。
/// </summary>
/// <returns>返回 size 数组。</returns>
public int[] GetSize()
{
return Size;
}
/// <summary>
/// 寻找一个结点所在的连通分量。
/// </summary>
/// <param name="p">需要寻找的结点。</param>
/// <returns>该结点所属的连通分量。</returns>
public override int Find(int p)
{
Validate(p);
while (p != Parent[p])
{
p = Parent[p];
ArrayParentVisitCount += 2;
}
ArrayParentVisitCount++;
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;
}
if (Size[rootP] < Size[rootQ])
{
Parent[rootP] = rootQ;
Size[rootQ] += Size[rootP];
}
else
{
Parent[rootQ] = rootP;
Size[rootP] += Size[rootQ];
}
ArrayParentVisitCount++;
ArraySizeVisitCount += 4;
TotalCount--;
}
}
Main 方法
var input = "9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2".Split(' ');
var weightedQuickUnion = new WeightedQuickUnionUf(10);
foreach (var s in input)
{
weightedQuickUnion.ResetArrayCount();
var numbers = s.Split('-');
var p = int.Parse(numbers[0]);
var q = int.Parse(numbers[1]);
weightedQuickUnion.Union(p, q);
var parent = weightedQuickUnion.GetParent();
for (var i = 0; i < parent.Length; i++)
{
Console.Write(parent[i] + " ");
}
Console.WriteLine("数组访问：" + weightedQuickUnion.ArrayParentVisitCount);
}