与以往的并查集不同，这次需要一个删除操作。如果是叶子节点还好，直接修改父亲指针就好。
但是如果要是移动根节点，指向它的所有子节点也会跟着变化。
所以要增加一个永远不会被修改的虚拟根节点，这样就可以把一个点从集合中删除而不影响其它的点了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 9 const int maxn = 200000 + 10; 10 11 int n, m; 12 13 LL sum[maxn]; 14 int cnt[maxn]; 15 int pa[maxn]; 16 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); } 17 18 int main() 19 { 20 while(scanf("%d%d", &n, &m) == 2 && n) 21 { 22 for(int i = 1; i <= n; i++) { pa[i] = i + n; sum[i + n] = i; cnt[i + n] = 1; } 23 for(int i = 1; i <= n; i++) pa[i + n] = i + n; 24 25 int op, x, y; 26 while(m--) 27 { 28 scanf("%d", &op); 29 if(op == 1) 30 { 31 scanf("%d%d", &x, &y); 32 int px = findset(x), py = findset(y); 33 if(px != py) 34 { 35 pa[px] = py; 36 sum[py] += sum[px]; 37 cnt[py] += cnt[px]; 38 } 39 } 40 else if(op == 2) 41 { 42 scanf("%d%d", &x, &y); 43 int px = findset(x), py = findset(y); 44 if(px != py) 45 { 46 pa[x] = py; 47 sum[py] += x; 48 sum[px] -= x; 49 cnt[py]++; cnt[px]--; 50 } 51 } 52 else 53 { 54 scanf("%d", &x); 55 int px = findset(x); 56 printf("%d %lld ", cnt[px], sum[px]); 57 } 58 } 59 } 60 61 return 0; 62 }