UVA 11987 Almost Unio-Find(削除操作付きで検索集)

Problem A
Almost Unio-Find
I hope you know the beautiful Unio-Find structure.In this proble,you're to implement something simiar,but not identical.
The data structure you need to write is also a collection of disject sets、supporting 3 operation:

1 p q

ユニオン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 elemens and the sum of elements in the set containing p.
Initially、the collection contains n sets:{1}、{2}、{3}、{n}
Input
The e e e e e are several test cases.Each test case begis with a ininininininininininininininintwo integers n and m(1<=n、m(=100,000)、the number of integers、and the number of commmands.Each of the nexxt m inininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininof input file does not exceed 5 MB.
Output
For each type-3 command 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

Explanion
Initially:{1}、{2}、{3}、{4}、{5}
Collection after operation 1 2:{1,2}、{3}、{4}、{5}
Collection after operation 2 3:｛1,2｝、｛3,4｝、｛5｝(we omit the empy set that is produced when taring out 3 from｛3｝)
Collection after operation 1 3:{1,2}、{3,4,5}
Collection after operation 2 4:{1,2,4}、{3,5}
 
 
最初はN個の集合があって、それぞれ1,2,3…nです.体操は三つあります
1:p q結合要素pとqのセット
2:p qはp要素をqセットに移動します.
3:pはp要素セットの個数と全部の要素の和を出力します.
 
考え方:1、3のステップに対して、2つの配列を探して記録すればいいです.
2の削除ステップについては、pのルートを直接qに向けてはいけない.pがあるセットのルートであれば、他のノードに影響を与えるからである.
したがって、pというノードは、集合に対して「影響なし」であり、新たにノード表示pが元のセットから逸脱したことを示すことができるので、もう一つの配列ID[p]を開いてpノードの現在の番号を表します.
 

#include
#include
const int maxn = 200010;

int fa[maxn],cnt[maxn],id[maxn];//  ，  ，  （      ）
long long sum[maxn];//  
int n,m,dep;

void init()
{
    for(int i = 0; i <= n; i ++)
    {
        sum[i] = fa[i] = id[i] = i;
        cnt[i] = 1;
    }
    dep = n;
}

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void unite(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
    sum[fy] += sum[fx];
    cnt[fy] += cnt[fx];
}

void move(int x)
{
    int fx = find(id[x]);     //   id[x]  x，    x    ，        
    sum[fx] -= x;            //  x     
    cnt[fx] --;              //  
    id[x] = ++ dep;
    sum[id[x]] = x;
    cnt[id[x]] = 1;
    fa[id[x]] = id[x];
}

int main()
{
//  freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int op,x,y;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            scanf("%d",&op);
            if(op == 1)
            {
                scanf("%d%d",&x,&y);
                if(find(id[x]) != find(id[y]))
                    unite(id[x],id[y]);
            }
            else if(op == 2)
            {
                scanf ("%d%d",&x,&y);
                if(find(id[x])!= find (id[y]))
                    move(x),unite(id[x],id[y]);
            }
            else
            {
                scanf("%d",&x);
                int fx = find(id[x]);
                printf("%d %lld
",cnt[fx],sum[fx]);
            }
        }
    }
    return 0;
}