1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int par[MAXN], rank[MAXN];

void Initialize(){
    int i=((N+1)<<1);
    while(i--){
        par[i]=i;
        rank[i]=1;
    }
}

int Find(int foo){ return foo==par[foo]?foo:(par[foo]=Find(par[foo])); }
char Same(int foo, int bar) { return Find(foo)==Find(bar); }
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x==y) return;
    if(rank[x]<rank[y]) par[x]=y;
    else {
        par[y]=x;
        if(rank[x]==rank[y]) ++rank[x];
    }
}