Article From:https://www.cnblogs.com/yzhhh/p/9969060.html

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 4x
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}


Idea: And search and delete. The relationship of the deleted node cannot be deleted in the original set because its children need it to contact the grandfather node. By establishing virtual nodes.

The operation before deletion replaces x with ID [x]. If there is a deletion operation, then the operation on X is to operate on ID [x].

PS:There is no real merge search deletion operation. Building a virtual number is equivalent to cloning a “deleted” node. There are still “deleted” nodes in the original set. Only the numbered nodes will be invoked later instead of the real nodes themselves.


 

#include<cstdio>
using namespace std;
int pre[200005],num[200005],sum[200005],id[100005];//idNumber nodes for virtual
int n,m,l;

void init(){
    l=n;
    for(int i=0;i<=n;i++){
        sum[i]=pre[i]=id[i]=i;
        num[i]=1;        
    }
} 

int find(int x){
    while(pre[x]!=x){
        int r=pre[x];
        pre[x]=pre[r];
        x=r;
    }
    return x;
}

void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)     {
    pre[fx]=fy;
    num[fy]+=num[fx];
    sum[fy]+=sum[fx];
    }
}

void move(int x){
    int fx=find(id[x]);// After removal, ID [x] is updated, but pre [x] can not be updated, so it can only use virtual nodes!
    sum[fx]-=x;            
    num[fx]--;             
    id[x]=++l; //xIs the L-N deleted nodes
    sum[id[x]]=x;
    num[id[x]]=1;
    pre[id[x]]=id[x];
}

int main(){
    int d,p,q;
    while(~scanf("%d%d",&n,&m)){
        init();    
        while(m--){
            scanf("%d%d",&d,&p);
            if(d==1){
                scanf("%d",&q);
                merge(id[p],id[q]);
            }
             else if(d==2){
                scanf("%d",&q);
                if(find(id[p])!=find(id[q])){            
                    move(p); 
                    merge(id[p],id[q]);        
                 }
            }
            else{
                int fp=find(id[p]);
                printf("%d %d\n",num[fp],sum[fp]);
            }
        }    
    }
    return 0;
} 

 


 

Leave a Reply

Your email address will not be published. Required fields are marked *