백준 1717 집합의 표현 C++

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

유니온파인드를 활용하는 문제이다.

주의할 점은, 항상 특정 노드의 최상위 부모가, 업데이트가 되어있지 않을 수 있다는 생각을 하고, 구현을 해야한다는 것이다.

따라서 최상위 부모를 찾으러 올라갈 때도, 항상 getParent 함수를 호출하면서 올라간다.

마찬가지로 union연산을 할 때에도, a혹은 b의 최상위 부모가 제대로 갱신이 되어있지 않을 수 있기 때문에 마찬가지로 갱신을 하면서 찾아준다.

#include<iostream>
using namespace std;
int r[1000002], n;
 
int getParent(int a) {// 마찬가지로 갱신하면서 찾으러 올라감
    if (r[a] == a) return r[a];
    else return r[a] = getParent(r[a]);
}
 
void join(int a, int b) { //갱신하면서
    r[getParent(a)] = getParent(b); //a의 부모를 b의 부모로 update 한다
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++)
        r[i] = i;
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            join(a, b);
        else if (cmd == 1) {
            //for (int i = 0; i <= n; i++) getParent(i);
            int pa = getParent(a);
            int pb = getParent(b);
            if (pa == pb) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    
    return 0;
}