1717 집합의 표현

유니온 파인드 처음으로 풀어보는 문제다. 개념을 처음 받아들일 땐 어렵지 않은 것 같은데 활용하기가 무진장 어려워 보인다.

<코드>

#include <stdio.h>
 
int n, m, d[1000001], ord, a, b;
 
int f(int x) {
    return x == d[x] ? x : d[x] = f(d[x]);
}
 
void u(int x, int y) {
    x = f(x);
    y = f(y);
    if (x != y) d[y] = x;
}
 
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) d[i] = i;
    while (m--) {
        scanf("%d%d%d", &ord, &a, &b);
        if (ord) 
            printf(f(a) == f(b) ? "YES\n" : "NO\n");
        else 
            u(a, b);
    }
    return 0;
}