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;
}
}