[C++/BOJ] 1717: 집합의 표현

✅ Gold 4
🔖 그래프

✏️ 1차 솔루션

합집합이면 같은 부모 노드를 갖는다고 가정
두 집합의 합치면 두 집합의 원소들의 부모 노드를 통일해주면 합집합과 같은 역할을 할 수 있음

🚨 1차 trouble

시간 초과 오류는 부모 노드 같은 노드들 수정할 때 for 문 써서 그런 것 같은데
답도 틀렸다 함,,원인을 못 찾겠음

✏️ 최종 솔루션

전체적인 풀이과정은 1차 솔루션과 유사한데 방법만 달라짐
int find(int node) 함수: 부모 노드 찾는 역할
node 의 부모 노드가 자기 자신일 경우는 node return
아닐 경우는 부모 노드가 따로 있다는 뜻이므로 root[node] 로 부모 노드 재귀 탐색

void uni(int a, int b) 함수
a 의 부모 노드를 find 함수로 찾아서 b 의 부모 노드로 갱신 -> 합집합하는 과정

📌 self feedback

int 함수에서 최종적인 return 값을 가장 deep 한 레벨의 return 값으로 받아오고 싶을 때는 무의미한 변수에 재귀함수 값 받으면 됨
예시

return root[node] = find(root[node]);

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;
 
vector<int>root;
 
int find(int node) {
    if (root[node] == node)
        return node;
    else
        return root[node] = find(root[node]);
}
 
void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    root[pb] = pa;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i <= n; i++)
        root.push_back(i);
 
    int cmd, a, b;
    for (int i = 0; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0) {
            uni(a, b); 
        }
        else {
            if (find(a) == find(b))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    
    return 0;
}