1.5.12 #
解答 #
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 的解答。
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)
{
var root = p;
while (root != Parent[root])
{
root = Parent[root];
}
while (p != root)
{
var newp = Parent[p];
Parent[p] = root;
p = newp;
}
return p;
}
}
Main 方法
var uf = new QuickUnionPathCompressionUf(10);
// 使用书中提到的最坏情况，0 连 1，1 连 2，2 连 3……
for (var i = 0; i < 4; i++)
{
uf.Union(i, i + 1);
}
var id = uf.GetParent();
for (var i = 0; i < id.Length; i++)
{
Console.Write(id[i]);
}
Console.WriteLine();