1.5.4 #
解答 #
对照输入和最坏输入均在书中出现，中文版见：P146，英文版见：P229。
样例输出：
3
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 8 9
size: 1 1 1 1 2 1 1 1 1 1
parent visit count:3
size visit count:4
8
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 5 6 7 4 9
size: 1 1 1 1 3 1 1 1 1 1
parent visit count:5
size visit count:4
5
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7 4 9
size: 1 1 1 1 3 1 2 1 1 1
parent visit count:3
size visit count:4
4
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 1 2 4 4 6 6 7 4 4
size: 1 1 1 1 4 1 2 1 1 1
parent visit count:3
size visit count:4
1
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 2 2 4 4 6 6 7 4 4
size: 1 1 2 1 4 1 2 1 1 1
parent visit count:3
size visit count:4
9
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 2 2 4 4 6 6 7 4 4
size: 1 1 2 1 4 1 2 1 1 1
parent visit count:6
size visit count:0
0
index: 0 1 2 3 4 5 6 7 8 9
parent: 6 2 2 4 4 6 6 7 4 4
size: 1 1 2 1 4 1 3 1 1 1
parent visit count:5
size visit count:4
2
index: 0 1 2 3 4 5 6 7 8 9
parent: 6 2 2 4 4 6 6 2 4 4
size: 1 1 3 1 4 1 3 1 1 1
parent visit count:3
size visit count:4
1
index: 0 1 2 3 4 5 6 7 8 9
parent: 6 2 6 4 4 6 6 2 4 4
size: 1 1 3 1 4 1 6 1 1 1
parent visit count:5
size visit count:4
0
index: 0 1 2 3 4 5 6 7 8 9
parent: 6 2 6 4 4 6 6 2 4 4
size: 1 1 3 1 4 1 6 1 1 1
parent visit count:8
size visit count:0
7
index: 0 1 2 3 4 5 6 7 8 9
parent: 6 2 6 4 4 6 6 2 4 4
size: 1 1 3 1 4 1 6 1 1 1
parent visit count:6
size visit count:0
-------------------------------------
1
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 2 3 4 5 6 7 8 9
size: 2 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
2
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 3 4 5 6 7 8 9
size: 3 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
3
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 4 5 6 7 8 9
size: 4 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
4
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 5 6 7 8 9
size: 5 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
5
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 0 6 7 8 9
size: 6 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
6
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 0 0 7 8 9
size: 7 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
7
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 0 0 0 8 9
size: 8 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
8
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 0 0 0 0 9
size: 9 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
9
index: 0 1 2 3 4 5 6 7 8 9
parent: 0 0 0 0 0 0 0 0 0 0
size: 10 1 1 1 1 1 1 1 1 1
parent visit count:3
size visit count:4
代码 #
Main 方法：
char[] split = { '\n', '\r' };
var inputReference = File.ReadAllText(DataFiles.TinyUf).Split(split, StringSplitOptions.RemoveEmptyEntries);
var inputWorst = File.ReadAllText(DataFiles.WorstUf).Split(split, StringSplitOptions.RemoveEmptyEntries);
RunTest(inputReference);
Console.WriteLine("-------------------------------------");
RunTest(inputWorst);
static void RunTest(string[] input)
{
var weightedQuickUnion = new WeightedQuickUnionUf(10);
var parent = weightedQuickUnion.GetParent();
var size = weightedQuickUnion.GetSize();
for (var i = 1; i < input.Length; i++)
{
var unit = input[i].Split(' ');
var p = int.Parse(unit[0]);
var q = int.Parse(unit[1]);
Console.WriteLine($"{p} {q}");
weightedQuickUnion.Union(p, q);
Console.Write("index:\t");
for (var j = 0; j < 10; j++)
{
Console.Write(j + " ");
}
Console.WriteLine();
Console.Write("parent:\t");
foreach (var m in parent)
{
Console.Write(m + " ");
}
Console.WriteLine();
Console.Write("size:\t");
foreach (var m in size)
{
Console.Write(m + " ");
}
Console.WriteLine();
Console.WriteLine("parent visit count:" + weightedQuickUnion.ArrayParentVisitCount);
Console.WriteLine("size visit count:" + weightedQuickUnion.ArraySizeVisitCount);
Console.WriteLine();
weightedQuickUnion.ResetArrayCount();
}
}