UVa 11987 并查集 Almost Union-Find

原文戳这

与以往的并查集不同，这次需要一个删除操作。如果是叶子节点还好，直接修改父亲指针就好。

但是如果要是移动根节点，指向它的所有子节点也会跟着变化。

所以要增加一个永远不会被修改的虚拟根节点，这样就可以把一个点从集合中删除而不影响其它的点了。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int maxn =  + ;

 int n, m;

 LL sum[maxn];

 int cnt[maxn];

 int pa[maxn];

 int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

 int main()

 {

     while(scanf("%d%d", &n, &m) ==  && n)

     {

         for(int i = ; i <= n; i++) { pa[i] = i + n; sum[i + n] = i; cnt[i + n] = ; }

         for(int i = ; i <= n; i++) pa[i + n] = i + n;

         int op, x, y;

         while(m--)

         {

             scanf("%d", &op);

             if(op == )

             {

                 scanf("%d%d", &x, &y);

                 int px = findset(x), py = findset(y);

                 if(px != py)

                 {

                     pa[px] = py;

                     sum[py] += sum[px];

                     cnt[py] += cnt[px];

                 }

             }

             else if(op == )

             {

                 scanf("%d%d", &x, &y);

                 int px = findset(x), py = findset(y);

                 if(px != py)

                 {

                     pa[x] = py;

                     sum[py] += x;

                     sum[px] -= x;

                     cnt[py]++; cnt[px]--;

                 }

             }

             else

             {

                 scanf("%d", &x);

                 int px = findset(x);

                 printf("%d %lld\n", cnt[px], sum[px]);

             }

         }

     }

     return ;

 }

代码君