UVA - 11987

?

Submit Status

Description

I hope you know the beautiful Union-Find structure. In this problem, you're to implement something similar, but not identical.

The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:

1 p q

Union the sets containing p and q. If p and q are already in the same set, ignore this command.

2 p q

Move p to the set containing q. If p and q are already in the same set, ignore this command

3 p

Return the number of elements and the sum of elements in the set containing p.

Initially, the collection contains n sets: {1}, {2}, {3}, ..., {n}.

Input

There are several test cases. Each test case begins with a line containing two integers n and m (1<=n,m<=100,000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1<=p,q<=n. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each type-3 command, output 2 integers: the number of elements and the sum of elements.

Sample Input

5 7
1 1 2
2 3 4
1 3 5
3 4
2 4 1
3 4
3 3

Output for the Sample Input

3 12
3 7
2 8

Explanation

Initially: {1}, {2}, {3}, {4}, {5}

Collection after operation 1 1 2: {1,2}, {3}, {4}, {5}

Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3})

Collection after operation 1 3 5: {1,2}, {3,4,5}

Collection after operation 2 4 1: {1,2,4}, {3,5}

Source

?

?

?

思路：1,3比较好实现，2则有点麻烦，2属于并查集的删除操作，需要另设一组real[]数组来确定元素的实际地址，每删除一个元素，就把这个元素放在最后面。。我本来以为直接把p指向q的根就行了，但发现这是错的。如果p是叶子结点，那可以，但如果是某个集合的根呢。我们只是要把这一个元素移掉，如果直接把p指向q的根，它的叶子节点们也过去啦。。。而如果另设一组real数组的话就可以将影响降为0啦。。

?

AC代码：

?

#include 
  
   
#include 
   
     #include 
    
      #define LL long long using namespace std; const int maxn = 200005; int pa[maxn], real[maxn], cnt[maxn]; int n, m, vnum; LL sum[maxn]; int find(int x) { return pa[x] != x ? pa[x] = find(pa[x]) : x; } void Union(int a, int b) { int a1 = find(real[a]), b1 = find(real[b]); pa[a1] = b1; sum[b1] += sum[a1]; cnt[b1] += cnt[a1]; } void Move(int a) { int t = find(real[a]); sum[t] -= a, cnt[t]--; real[a] = ++vnum; //并查集的这里到n了，所以要先++，之前后++的样例没过，检查半天=_=|| sum[real[a]] = a, cnt[real[a]] = 1, pa[real[a]] = real[a]; } int main() { while(scanf("%d %d", &n, &m) != EOF) { for(int i = 0; i <= n; i++) { pa[i] = real[i] = sum[i] = i; cnt[i] = 1; } vnum = n; int ord, p, q; while(m--) { scanf("%d", &ord); if(ord == 1) { scanf("%d %d", &p, &q); if(find(real[p]) != find(real[q])) Union(p, q); } else if(ord == 2) { scanf("%d %d", &p, &q); if(find(real[p]) != find(real[q])) Move(p), Union(p, q); } else if(ord == 3) { scanf("%d", &p); int tmp = find(real[p]); printf("%d %lld\n", cnt[tmp], sum[tmp]); } } } return 0; } 
    
   
  

?

?

?

?

?

?