[UVA] 11987 - Almost Union-Find

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11987 - Almost Union-Find
Source            : UVA Online Judge
Category          : Data Structure
Algorithm         : Disjoint Set Union
Verdict           : Accepted

1. #include <bits/stdc++.h>  
2.   
3. using namespace std;  
4.   
5. static const int maxn = 3e5 + 5;  
6.   
7. struct node  
8. {  
9.     int ele, sum, father, ffather;  
10.     node(int ele = 0, int sum = 0, int father = 0, int ffather) :  
11.           ele(ele), sum(sum), father(father), ffather(ffather) {}  
12. } ff[maxn];  
13.   
14. void makeSet(int n)  
15. {  
16.     for (int i = 1; i <= n; i++)  
17.     {  
18.         ff[i].ele = ff[n+i].ele = 1;  
19.         ff[i].sum = ff[n+i].sum = i;  
20.         ff[i].father = ff[n+i].father = n+i;  // father  
21.     }  
22. }  
23.   
24. int findRep(int r)  
25. {  
26.     if (ff[r].father == r) return ff[r].father;  
27.     return ff[r].father = findRep(ff[r].father);  
28. }  
29.   
30. void Union(int u, int v)  
31. {  
32.     int p = findRep(u);  
33.     int q = findRep(v);  
34.     if (p == q) return;  
35.     ff[q].ele += ff[p].ele; ff[p].ele = 0;  
36.     ff[q].sum += ff[p].sum; ff[p].sum = 0;  
37.     ff[p].father = q;  
38. }  
39.   
40. void Move(int u, int v)  
41. {  
42.     int p = findRep(u);  
43.     int q = findRep(v);  
44.     if (p == q) return;  
45.     ff[q].ele += 1;  
46.     ff[q].sum += u;  
47.     ff[p].ele -= 1;  
48.     ff[p].sum -= u;  
49.     ff[u].father = q;  
50. }  
51.   
52. void Res(int u)  
53. {  
54.     int p = findRep(u);  
55.     printf("%d %d\n", ff[p].ele, ff[p].sum);  
56. }  
57.   
58. int main()  
59. {  
60.     //freopen("in.txt", "r", stdin);  
61.   
62.     int n, q;  
63.     while (scanf("%d %d", &n, &q) == 2)  
64.     {  
65.         makeSet(n);  
66.         while (q--)  
67.         {  
68.             int type;  
69.             scanf("%d", &type);  
70.             if (type == 1)  
71.             {  
72.                 int u, v;  
73.                 scanf("%d %d", &u, &v);  
74.                 Union(u, v);  
75.             }  
76.             else if (type == 2)  
77.             {  
78.                 int u, v;  
79.                 scanf("%d %d", &u, &v);  
80.                 Move(u, v);  
81.             }  
82.             else if (type == 3)  
83.             {  
84.                 int u;  
85.                 scanf("%d", &u);  
86.                 Res(u);  
87.             }  
88.         }  
89.     }  
90. }