1.5.4

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

对照输入和最坏输入均在书中出现,中文版见: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 方法:

using System;
using UnionFind;

namespace _1._5._4
{
    /*
     * 1.5.4
     * 
     * 在正文的加权 quick-union 算法示例中,
     * 对于输入的每一对整数(包括对照输入和最坏情况下的输入),
     * 给出 id[] 和 sz[] 数组的内容以及访问数组的次数。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            char[] split = { '\n', '\r' };
            string[] inputReference = TestCase.Properties.Resources.tinyUF.Split(split, StringSplitOptions.RemoveEmptyEntries);
            string[] inputWorst = TestCase.Properties.Resources.worstUF.Split(split, StringSplitOptions.RemoveEmptyEntries);

            RunTest(inputReference);
            Console.WriteLine("-------------------------------------");
            RunTest(inputWorst);
        }

        static void RunTest(string[] input)
        {
            var weightedQuickUnion = new WeightedQuickUnionUF(10);
            int n = int.Parse(input[0]);
            int[] parent = weightedQuickUnion.GetParent();
            int[] size = weightedQuickUnion.GetSize();

            for (int i = 1; i < input.Length; ++i)
            {
                string[] unit = input[i].Split(' ');
                int p = int.Parse(unit[0]);
                int q = int.Parse(unit[1]);

                Console.WriteLine($"{p} {q}");
                weightedQuickUnion.Union(p, q);

                Console.Write("index:\t");
                for (int j = 0; j < 10; ++j)
                {
                    Console.Write(j + " ");
                }
                Console.WriteLine();

                Console.Write("parent:\t");
                foreach (int m in parent)
                {
                    Console.Write(m + " ");
                }
                Console.WriteLine();
                Console.Write("size:\t");
                foreach (int 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();
            }
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题