UVa 11987

Almost Union-Find

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Intermediate

Problem

众所周知，有一种漂亮的数据结构叫并查集。请你实现一种与并查集十分相似的结构，该结构的支持以下三种操作：

• 1 p q 将元素p和q所在的集合相交，如果p和q已经在同一个集合中，则忽略该操作。
• 2 p q 将元素q加入到p所在的集合中，如果p和q已经在同一集合中，则忽略该操作。
• 3 p 输出元素p所在的集合中，元素的个数和元素之和。

一开始，有n个集合，分别是{1}，{2}，...，{n}。

Input

输入有多组样例，每组样例的第一行是两个整数 n 和 m （1 ≤ n , m ≤ 100,000），分别表示元素个数和操作次数，以下 m 行每行是一个操作，对于每个操作， 1 ≤ p , q ≤ n 。输入EOF表示结束，输入文件不大于5MB。

Output

对于所有第三种操作，按要求输出元素的个数和元素之和。

Solution

这道题需要我们在并查集的基础上稍作修改。首先，对于第一种操作，并查集本身就已经符合条件。第三种操作，我们只需要利用一个 num[x] 和一个 sum[x] 记录以 x 元素为代表元的时候，该集合的元素个数和元素之和，然后在并查集做其他两种操作时，做对应的修改即可。现在，剩下最难的第二种操作，我们可以这样来做：

对于操作 2 p q 我们需要先将q元素从集合中删除，然后将q添加到p所在集合中。后者的操作利用并查集可以很轻松的完成，但是对于前一种操作，我们则需要稍费脑筋。

假如我们真的要删除q元素，则在并查集中，需要将q元素的所有儿子结点变成其父亲结点的儿子结点，那么我们不得不添加新的存储空间来保存每个结点的孩子。一旦如此，我们还需要考虑如何从q元素的父亲结点删除q元素这个儿子。这样一来，不但操作变麻烦，时间复杂度也提高了，最终导致程序TLE。

所以，我们应该换一种角度，我们并不真正地删除q元素，而是首先将q元素对集合造成的影响消除（即修改其集合代表元的 num 和 sum 值），然后将q元素所在的结点当作一个没有任何含义的结点，依然保存着。这时候，我们新建一个q元素，将其加入到p所在的集合即可。对于这个实现，我们需要一个 id[x] 来表示 x 元素当前所在的结点编号。