[자료구조] 백준 1717번: 집합의 표현 (C++)

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

1717번: 집합의 표현

분리 집합(Disjoint Set)은 Union-Find기법으로 처리할 수 있다.

union: 집합을 합침
find:어떤 두 원소가 하나의 집합에 속해있는지 확인

 

허나, 이 Union-Find는 이미 Kruskal's Algorithm을 공부하면서 알게 되었었다.

https://draw-code-boy.tistory.com/197

[알고리즘] 최소 스패닝 트리 (C++), 크루스칼 알고리즘

 

[AC 코드]

#include <iostream>
#include <vector>
#define MAX_V (1000000 + 1)
using namespace std;

int n, m;
int root[MAX_V];

int getRoot(int node){
    if(root[node] == node) return node;
    return root[node] = getRoot(root[node]);
}

void unionNode(int a, int b){
    int rootA = getRoot(a);
    int rootB = getRoot(b);
    
    if(rootA > rootB){
        root[rootA] = rootB;
    }
    else{
        root[rootB] = rootA;
    }
}

bool find(int a, int b){
    int rootA = getRoot(a);
    int rootB = getRoot(b);
    
    if(rootA == rootB) return true;
    else return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i <= n; i++){
        root[i] = i;
    }
    
    for(int i = 0; i < m; i++){
        int q, a, b;
        cin >> q >> a >> b;
        if(q == 0){
            unionNode(a, b);
        }
        else{
            if(find(a, b)){
                cout << "YES" << '\n';
            }
            else{
                cout << "NO" << '\n';
            }
        }
    }
    
    return 0;
}