1.5.17

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

解答

官方给出的 ErdosRenyi:ErdosRenyi.java
为了方便之后做题,除了 Count() 之外,这个类还包含其他方法,具体可以查看注释。

代码

ErdosRenyi.cs

using System;
using System.Collections.Generic;

namespace UnionFind
{
    /// <summary>
    /// 提供一系列对并查集进行随机测试的静态方法。
    /// </summary>
    public class ErdosRenyi
    {
        /// <summary>
        /// 随机生成一组能让并查集只剩一个连通分量的连接。
        /// </summary>
        /// <param name="n">并查集大小。</param>
        /// <returns>一组能让并查集只剩一个连通分量的连接。</returns>
        public static Connection[] Generate(int n)
        {
            Random random = new Random();
            List<Connection> connections = new List<Connection>();
            WeightedQuickUnionPathCompressionUF uf = new WeightedQuickUnionPathCompressionUF(n);

            while (uf.Count() > 1)
            {
                int p = random.Next(n);
                int q = random.Next(n);
                uf.Union(p, q);
                connections.Add(new Connection(p, q));
            }

            return connections.ToArray();
        }

        /// <summary>
        /// 随机生成连接,返回令并查集中只剩一个连通分量所需的连接总数。
        /// </summary>
        /// <param name="uf">用于测试的并查集。</param>
        /// <returns>需要的连接总数。</returns>
        public static int Count(UF uf)
        {
            Random random = new Random();
            int size = uf.Count();
            int edges = 0;
            while (uf.Count() > 1)
            {
                int p = random.Next(size);
                int q = random.Next(size);
                uf.Union(p, q);
                edges++;
            }

            return edges;
        }

        /// <summary>
        /// 使用指定的连接按顺序合并。
        /// </summary>
        /// <param name="uf">需要测试的并查集。</param>
        /// <param name="connections">用于输入的连接集合。</param>
        public static void Count(UF uf, Connection[] connections)
        {
            foreach (Connection c in connections)
            {
                uf.Union(c.P, c.Q);
            }
        }
    }
}

Main 方法:

using System;
using UnionFind;

namespace _1._5._17
{
    /*
     * 1.5.17
     * 
     * 随机链接。
     * 设计 UF 的一个用例 ErdosRenyi,
     * 从命令行接受一个整数 N,在 0 到 N-1 之间产生随机整数对,
     * 调用 connected() 判断它们是否相连,
     * 如果不是则调用 union() 方法(和我们的开发用例一样)。
     * 不断循环直到所有触点均相互连通并打印出生成的连接总数。
     * 将你的程序打包成一个接受参数 N 并返回连接总数的静态方法 count(),
     * 添加一个 main() 方法从命令行接受 N,调用 count() 并打印它的返回值。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int N = 10;
            int[] edges = new int[5];
            for (int i = 0; i < 5; ++i)
            {
                var uf = new UF(N);
                Console.WriteLine(N + "\t" + ErdosRenyi.Count(uf));
                N *= 10;
            }
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题