백준 1717 집합의 표현 - C++, Union find

1717번: 집합의 표현

#include <iostream>
using namespace std;
int parent[1000001];

int FindParent(int x){
    if(x == parent[x])
        return x;

    return parent[x] = FindParent(parent[x]);
}

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    else
        parent[y] = x;
}

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++)
        parent[i] = i;
    
    while(m--){
        int operand, a, b;
        cin >> operand >> a >> b;

        if(operand == 0){
            Merge(a, b);
        } else{
            if(FindParent(a) == FindParent(b))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}

 

---

Union Find의 개념만 알고 있어도 풀 수 있는 문제였습니다. 일단 노드의 부모를 전부 자기 자신으로 초기화한 뒤 Merge와 FindParent 함수를 통해 각각 유니온, 파인드를 하게 했습니다.

 

 

<FindParent>

 

int FindParent(int x){
    if(x == parent[x])
        return x;

    return parent[x] = FindParent(parent[x]);
}

 

 해당 노드의 부모를 찾을 때 까지 재귀적으로 부모를 찾아가게 됩니다. 최종 부모는 자기 자신을 부모로 하고 있기 때문에 if문에서 걸러져서 나오게 됩니다.

 

 

<Merge>

 

void Merge(int x, int y){
    x = FindParent(x);
    y = FindParent(y);

    if(x == y)
        return;
    else
        parent[y] = x;
}

 

 두 집합을 합치는 함수로 먼저 두 노드의 최종 부모를 찾아오게 합니다. 그런 다음 부모가 같다면 이미 같은 집합이니 바로 리턴, 다르다면 x의 부모로 편입시켰습니다.