SPOJ_PTIT_DSA/BCBIN.cpp at master · hoaf13/SPOJ_PTIT_DSA · 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
/*
 * =====================================================================================
 *
 *       Filename:  BCBIN.cpp
 *
 *    Description:  DSU
 *
 *        Version:  1.0
 *        Created:  08/09/2019 22:37:07
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  hoaf13 (paxd), gam.nhosmiles2000@gmail.com
 *        Company:  Posts and Telecommunications Institute of Technology
 *					-ProPTIT
 * =====================================================================================
 */

#include<iostream>

using namespace std;

const int N = 10004;
int par[N], rankz[N];


void init() {
    for (int i=0; i<N; i++) {
        par[i] = i;
        rankz[i] = 0;
    }
}

int find(int u) {
    if (par[u] != u) par[u] = find(par[u]);
    return par[u];
}

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (rankz[u] == rankz[v]) rankz[u]++;
    if (rankz[u] < rankz[v]) par[u] = v;
    else par[v] = u;
}

int main(){
    init();
    int Q;
    cin >> Q;
    while(Q--){
        int u,v,t;
        cin >> u >> v >> t;
        if (t == 1){
            join(u,v);
        }
        else{
            u = find(u);
            v = find(v);
            if (u == v){
                cout << 1 << endl;
            }
            else{
                cout << 0 << endl;
            }
        }
    }


}