1.5.8 # 解答 # 当有多个元素需要修改的时候，这个直观算法可能会出现错误。 例如如下情况： index 0 1 2 3 4 5 6 7 8 9 id 0 0 0 0 0 5 5 5 5 5 输入 0, 5 i = 0 时，id[i] == id[p]，此时 id[i] = id[q]。 数组变为 5 0 0 0 0 5 5 5 5 5 i = 1 时，id[i] != id[p]，算法出现错误。 只要在 id[p] 之后还有需要修改的元素，那么这个算法就会出现错误。
1.5.9 # 解答 # 不可能。 树如下所示。 由于加权 quick-union 算法任意节点的最大深度为 lgN （节点总数为 N）。 （这个结论可以在中文版 P146，或者英文版 P228 找到） 上面这个树的最大深度为 4 > lg10 因此这棵树不可能是通过加权 quick-union 算法得到的。
1.5.10 # 解答 # 本题答案已经给出，也很好理解。 如果合并时只是把子树挂到结点 q 上而非其根节点， 树的高度会明显增加，进而增加每次 Find() 操作的开销。
1.5.11 # 解答 # 类似于加权 quick-union 的做法，新增一个 size[] 数组以记录各个根节点的大小。 每次合并时先比较一下两棵树的大小，再进行合并。 这样会略微减少赋值语句的执行次数，提升性能。 代码 # WeightedQuickFindUF.cs /// <summary> /// 用加权 QuickFind 算法实现的并查集。 /// </summary> public class WeightedQuickFindUf { private readonly int[] _size; // 记录每个连通分量的大小。 private readonly int[] _id; // 记录每个结点的连通分量。 private int _count;// 连通分量总数。 public int ArrayVisitCount { get; private set; } //记录数组访问的次数。 /// <summary> /// 新建一个使用加权 quick-find 实现的并查集。 /// </summary> /// <param name="n">并查集的大小。</param> public WeightedQuickFindUf(int n) { _count = n; _id = new int[n]; _size = new int[n]; for (var i = 0; i < n; i++) { _id[i] = i; _size[i] = 1; } } /// <summary> /// 重置数组访问计数。 /// </summary> public void ResetArrayCount() { ArrayVisitCount = 0; } /// <summary> /// 表示并查集中连通分量的数量。 /// </summary> /// <returns>返回并查集中连通分量的数量。</returns> public int Count() { return _count; } /// <summary> /// 寻找 p 所在的连通分量。 /// </summary> /// <param name="p">需要寻找的结点。</param> /// <returns>返回 p 所在的连通分量。</returns> public int Find(int p) { Validate(p); ArrayVisitCount++; return _id[p]; } /// <summary> /// 判断两个结点是否属于同一个连通分量。 /// </summary> /// <param name="p">需要判断的结点。</param> /// <param name="q">需要判断的另一个结点。</param> /// <returns>如果属于同一个连通分量则返回 true，否则返回 false。</returns> public bool IsConnected(int p, int q) { Validate(p); Validate(q); ArrayVisitCount += 2; return _id[p] == _id[q]; } /// <summary> /// 将两个结点所在的连通分量合并。 /// </summary> /// <param name="p">需要合并的结点。</param> /// <param name="q">需要合并的另一个结点。</param> public void Union(int p, int q) { Validate(p); Validate(q); var pId = _id[p]; var qId = _id[q]; ArrayVisitCount += 2; // 如果两个结点同属于一个连通分量，那么什么也不做。 if (pId == qId) { return; } // 判断较大的连通分量和较小的连通分量。 int larger; int smaller; if (_size[pId] > _size[qId]) { larger = pId; smaller = qId; _size[pId] += _size[qId]; } else { larger = qId; smaller = pId; _size[qId] += _size[pId]; } // 将较小的连通分量连接到较大的连通分量上， // 这会减少赋值语句的执行次数，略微减少数组访问。 for (var i = 0; i < _id. ...
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. ...
1.5.13 # 解答 # 官方实现：WeightedQuickUnionPathCompressionUF。 加权 quick-union 中，两个大小相等的树合并可以有效增加高度，同时输入必须保证是根节点以规避路径压缩。 代码 # WeightedQuickUnionPathCompressionUF.cs 从 WeightedQuickUnionUF.cs 继承，详情参见 1.5.3 的解答。 public class WeightedQuickUnionPathCompressionUf : WeightedQuickUnionUf { /// <summary> /// 新建一个大小为 n 的并查集。 /// </summary> /// <param name="n">新建并查集的大小。</param> public WeightedQuickUnionPathCompressionUf(int n) : base(n) { Size = new int[n]; for (var i = 0; i < n; i++) { Size[i] = 1; } } /// <summary> /// 寻找一个结点所在的连通分量。 /// </summary> /// <param name="p">需要寻找的结点。</param> /// <returns>该结点所属的连通分量。</returns> public override int Find(int p) { Validate(p); var root = p; while (root ! ...
1.5.14 # 解答 # WeightedQuickUnionByHeight 的官方实现：WeightedQuickUnionByHeightUF.java。 证明： 一次 Union 操作只可能发生如下两种情况。 两棵树的高度相同，这样合并后的新树的高度等于较大那棵树的高度 + 1。 两棵树的高度不同，这样合并后的新树高度等于较大那棵树的高度。 现在证明通过加权 quick-union 算法构造的高度为 h 的树至少包含 2h 个结点。 基础情况，高度 h = 0, 结点数 k = 1。 为了使高度增加，必须用一棵高度相同的树合并，而 h = 0 时结点数一定是 1，则： h = 1, k = 2 由于两棵大小不同的树合并，最大高度不会增加，只会增加结点数。 因此，每次都使用相同高度的最小树进行合并，有： h = 2, k = 4 h = 3, k = 8 h = 4, k = 16 ...... 递推即可得到结论，k ≥ 2^h 因此 h <= lgk ...
1.5.15 # 解答 # 首先证明在最坏情况下加权 quick-union 算法生成的树中的每一层结点数均为二项式系数。 最坏情况下，每次 union 操作都是合并相同大小的树，如下图所示： 设第 i 层的结点数为 ki，那么最坏情况下每次合并后的 ki’ = ki + ki-1 。 这符合二项式系数的构造特点（详情可以搜索杨辉三角）， 第一个结论证明完毕。 接下来求平均深度，首先根据二项式的求和公式，一棵深度为 n 的树（根结点的深度为零）结点总数为： $$ \sum_{k=0}^{n} \begin{pmatrix} n \newline k \end{pmatrix} =2^n $$ 每层结点数 × 该层深度后的和为： $$ \sum_{k=0}^{n}k \cdot \begin{pmatrix} n \newline k \end{pmatrix}=n\sum_{k=1}^{n} \begin{pmatrix} n-1 \newline k-1 \end{pmatrix}=n\sum_{s=0}^{n-1} \begin{pmatrix} n-1 \newline s \end{pmatrix}=n2^{n-1} $$ 这里用到了这个公式化简： $$ \begin{pmatrix} n \newline k \end{pmatrix}=\frac{n}{k} \begin{pmatrix} n-1 \newline k-1 \end{pmatrix} $$ ...
1.5.16 # 解答 # 给出绘图结果样例： 代码 # 仅给出绘图相关的代码，窗体部分见 github 上的代码： using System; using System.Linq; using System.Windows.Forms; using System.Drawing; using UnionFind; namespace _1._5._16 { static class Program { [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Compute(); Application.Run(new Form1()); } static void Compute() { char[] split = { '\n', '\r' }; string[] input = TestCase.Properties.Resources.mediumUF.Split(split, StringSplitOptions.RemoveEmptyEntries); int size = int.Parse(input[0]); QuickFindUF quickFind = new QuickFindUF(size); QuickUnionUF quickUnion = new QuickUnionUF(size); string[] pair; int p, q; int[] quickFindResult = new int[size]; int[] quickUnionResult = new int[size]; for (int i = 1; i < size; ++i) { pair = input[i]. ...
1.5.17 # 解答 # 官方给出的 ErdosRenyi：ErdosRenyi.java。 为了方便之后做题，除了 Count() 之外，这个类还包含其他方法，具体可以查看注释。 代码 # ErdosRenyi.cs public class ErdosRenyi { /// <summary> /// 随机生成一组能让并查集只剩一个连通分量的连接。 /// </summary> /// <param name="n">并查集大小。</param> /// <returns>一组能让并查集只剩一个连通分量的连接。</returns> public static Connection[] Generate(int n) { var random = new Random(); var connections = new List<Connection>(); var uf = new WeightedQuickUnionPathCompressionUf(n); while (uf.Count() > 1) { var p = random.Next(n); var 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) { var random = new Random(); var size = uf. ...