Competitive_Programming/DisjointSet.cpp at master · apsc/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<stdio.h>
int a[10],weight[10];

void quickFind(int i, int j){
     int p=a[i],q=a[j];
     for(int k=0;k<10;k++){
             if(a[k]==p){
                            a[k]=q;
             }
     }
}
int root(int c){
    while(c!=a[c])c=a[c];
    return c;
}
void quickUnion(int j,int i){
     int p=root(i);
     int q=root(j);
     if(weight[p]>weight[q]){a[q]=p;weight[p]+=weight[q];}
     else{
          a[p]=q;
          weight[q]+=weight[p];
     }
}
void quickUnionUpgrade(int i,int j){}
int main(){
    for(int i=0;i<10;i++){
            a[i]=i;
    }
    int i=0,j;
    scanf("%d%d",&i,&j);
    while(i<10){

                quickFind(i,j);

                scanf("%d%d",&i,&j);
    }


    for(int i=0;i<10;i++){
            printf("%d ",a[i]);
    }

    for(int l=0;l<10;l++){
            a[l]=l;
            weight[l]=1;
    }


    i=0,j;
    scanf("%d%d",&i,&j);
    while(i<10){
               quickUnion(i,j);

                scanf("%d%d",&i,&j);
    }

    for(int i=0;i<10;i++){
            printf("%d ",a[i]);
    }


    for(int i=0;i<10;i++){
            a[i]=i;
    }
    i=0,j;
    scanf("%d%d",&i,&j);
    while(i<10){

                quickFind(i,j);
                scanf("%d%d",&i,&j);
    }

    return 0;
}