백준 1717번 집합의 표현 C++ 유니온 파인드

리뷰

유니온 파인드의 기초적인 문제

 

문제 풀이

1. 노드는 최대 100만개 까지 입력받을 수 있으므로 nodes 배열을 1000001 크기로 초기화 해준다.
2. 이후 각 노드에 자기 자신을 value로 받도록 값을 입력해 준다.
3. 이후 쿼리를 입력받아 a가 0일 경우 b와 c를 Union 함수의 인자로 보내고, a가 1일 경우 Find 함수의 인자로 보낸다.
4. Union은 입력받은 두 노드를 Find를 통해 루트 노드를 받아온 뒤 만약 두 노드의 루트가 같다면 return 아닐 경우 뒤 노드의 루트를 앞 노드의 루트로 바꾸어 준다.
5. Find는 루트 노드를 찾을 때 까지 재귀를 통해 노드를 탐색해 준다. 이때 재귀를 빠져나오며 경로에 있는 노드의 value를 루트 노드로 갱신해 준다.
6. 만약 a가 1일때 b와 c를 Find한 값이 동일하다면 루트가 같은 노드이므로 YES를, 다를 경우 NO를 출력해 준다.

 

참고 사항

5번에서 진행하는 부분이 경로를 압축해 주어 더 빠른 탐색이 가능하게 해준다. (재귀가 깊어지지 않는다.)

 

 

정답 코드

#include<iostream>

using namespace std;

int n, m;
int nodes[1000001];

int Find(int a) {
    if (nodes[a] == a) return a;
    return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
    int rootA = Find(a);
    int rootB = Find(b);
    if (rootA == rootB) return;
    nodes[rootB] = rootA;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        nodes[i] = i;
    }

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        if (!a) Union(b, c);
        else {
            if (Find(b) == Find(c)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}