1717번: 집합의 표현

https://www.acmicpc.net/problem/1717


$O(n+m\alpha (n))$

union-find 자료구조를 사용한다.

#include<cstdio>
int n, m, p[1000001];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) p[i] = i;
    for (int i = 0, x, y, z; i<m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        x ? puts(f(y) ^ f(z) ? "NO" : "YES") : p[f(y)] = f(z);
    }
    return 0;
}