P3367 【模板】并查集

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
#include<cstdio>
#define re register
const int MAXn = 1e4;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c >'9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;  
}

int fa[MAXn + 10];
int anc(int x) {
    return fa[x] = fa[x] == x ? x : anc(fa[x]);
}
void Merge(int x, int y) {
    if (anc(x) != anc(y)) {
        fa[anc(x)] = y;
    }
}
bool SameAnc(int x, int y) {
    return anc(x) == anc(y);
}
void Init(int top) {
    for (re int i = 1; i <= top; ++i) {
        fa[i] = i;
    }
}

int n, m;
int main() {
    read(n), read(m);
    Init(n);
    for (re int i = 1, opt, x, y; i <= m; ++i) {
        read(opt);
        switch (opt) {
        case 1:
            read(x), read(y);
            Merge(x, y);
            break;
        case 2:
            read(x), read(y);
            SameAnc(x, y) ? printf("Y\n") : printf("N\n");
            break;
        }
    }
}