UVA - 11987 Almost Union-Find[并查集删除]-白红宇

UVA - 11987 Almost Union-Find[并查集删除]

阅读量：7186 次

发布时间：2019-06-29

本文共 2943 字，大约阅读时间需要 9 分钟。

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:

1pq	Union the sets containing p and q. If p and q are already in the same set, ignore this command.
2pq	Move p to the set containing q. If p and q are already in the same set, ignore this command.
3p	Return the number of elements and the sum of elements in the set contain- ing 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).

Output

For each type-3 command, output 2 integers: the number of elements and the sum of elements.

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}

Sample Input

5 7

1 1 2

2 3 4

1 3 5

3 4

2 4 1

3 4

3 3

Sample Output

3 12 37 28

白书

删除操作

用一个id，删除时给被删除的点重新分配id，旧的父亲和新的父亲分别更新行了

注意本题权值就是自己

沙茶的查询忘加id了.............

////  main.cpp//  uva11987////  Created by Candy on 10/12/16.//  Copyright © 2016 Candy. All rights reserved.//#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            using namespace std;const int N=1e5+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
      if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,m,op,p,q;int fa[N],sum[N],id[N],cnt[N],num=0;inline int find(int x){
      return x==fa[x]?x:fa[x]=find(fa[x]);}inline void unn(int x,int y){    int f1=find(id[x]),f2=find(id[y]);    if(f1!=f2){        fa[f1]=f2;        sum[f2]+=sum[f1];        cnt[f2]+=cnt[f1];    }}inline void move(int x,int y){    int f1=find(id[x]),f2=find(id[y]);    if(f1!=f2){        sum[f1]-=x;        cnt[f1]--;        id[x]=++num;        sum[f2]+=x;        cnt[f2]++;        fa[id[x]]=f2;    }}int main(int argc, const char * argv[]) {    while(scanf("%d%d",&n,&m)!=EOF){        num=n;        for(int i=1;i<=n;i++) {fa[i]=sum[i]=id[i]=i;cnt[i]=1;}        for(int i=1;i<=m;i++){            op=read();            if(op==1){                p=read();q=read();                unn(p,q);            }else if(op==2){                p=read();q=read();                move(p,q);            }else{                p=read();                p=find(id[p]);                printf("%d %d\n",cnt[p],sum[p]);            }        }    }        return 0;}

转载地址：http://gdykm.baihongyu.com/

你可能感兴趣的文章