四、假设想要增加一个 PRINT-SET(x) 操作，它是对于给定的结点 x 打印出 x 所在集合的所有成员，顺序可以任意。如何对一棵不相交集合森林的每个结点仅增加一个属性，使得 PRINT-SET(x) 所花费的时间同 x 所在集合元素的个...

三、给出一个包含 m 个 MAKE-SET 、UNION 和 FINDSET 操作的序列(其中有 n 个是 MAKE-SET 操作)，当仅使用按秩合并时，需要 Ω(mlgn) 的时间。如果要写代码，请用go语言。...

二、写出使用路径压缩的 FIND-SET 过程的非递归版本。如果要写代码，请用go语言。

一、用按秩合并与路径压缩启发式策略的不相交集合森林重做练习21.2-2。如果要写代码，请用go语言。

六、假设对 UNION 过程做一个简单的改动，在采用链表表示中拿掉让集合对象的 tail 指针总指向每个表的最后一个对象的要求。无论是使用还是不使用加权合并启发式策略，这个修改不应该改变 UNION 过程的渐近运行时间。(提...

五、Gompers 教授猜想也许有可能在每个集合对象中仅使用一个指针，而不是两个指针( head 和 tail )，同时仍然保留每个链表元素的2个指针。请说明教授的猜想是有道理的，并通过描述如何使用一个链表来表示每个集合，使得每个...

四、请给出图 21-3 所示操作序列的一个运行时间的渐近紧确界，假定使用链表表示和加权合并启发式策略。如果要写代码，请用go语言。

二、对定理 21.1 的整体证明进行改造，得到使用链表表示和加权合并启发式策略下的 MAKE-SET 和 FIND-SET 的摊还时间上界为 O(1)，以及 UNION 的摊还时间上界为 O(lgn)。如果要写代码，请用go语言。...

三、在 CONNECTED-COMPONENTS 作用于一个有 k 个连通分量的无向图 G=(V，E) 的过程中，FIND-SET 需要调用多少次？ UNION 需要调用多少次？用 |V| 、 |E| 和 k 来表示你的答案。如果要写代码，请用go语言。...

三、在 CONNECTED-COMPONENTS 作用于一个有 k 个连通分量的无向图 G=(V，E) 的过程中，FIND-SET 需要调用多少次？ UNION 需要调用多少次？用 |V| 、 |E| 和 k 来表示你的答案。如果要写代码，请用go语言。...