[백준]1717번 집합의표현 - C++

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

1717번: 집합의 표현

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

---

Disjoint Set을 활용하여 풀 수 있다.

#include <iostream>

using namespace std;

int n,m,op,a,b;
int parent[1000001];

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

void Union(int x, int y){
    int xp = Find(x);
    int yp = Find(y);
    if(xp != yp){
        if(xp <= yp)
            parent[yp] = xp;
        else
            parent[xp] = yp;
    }
}

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0 ; i <= n ; i++)
        parent[i] = i;
    for(int i = 0 ; i < m; i++){
        cin >> op >> a >> b;
        if(op == 0){
            Union(a,b);
        }
        else if(op == 1){
            if(Find(a) != Find(b))
                cout << "NO\n";
            else
                cout << "YES\n";
        }
    }
}

---

제목부터 분리 집합을 활용하고 싶게 만드는 문제이다. 분리집합 문제를 한번 풀어봐야지 했는데 안 걸리다가 이번에 풀게 되었다! 한 번에 풀이를 적었고 잘 나오는 것 같았는데 시간초과가 나왔다. Path compression까지 했으니 시간초과가 나지 않을 줄 알아서 생각을 해보니 tie 설정을 안 해서 그랬다. 그래서 고치고 나니 틀렸습니다가 나왔다! 알고리즘을 아무리 봐도 틀린 이유가 보이지 않았는데 오랫동안 보다 보니 YES 혹은 yes로 적었어야 했는데 Yes로 적은 것이다. 심지어 질의응답에 누가 No를 써서 틀려서 웃고 넘어갔는데 이런 일이 일어날 줄은 몰랐다. 알고리즘적으로 말고 이런 것으로 틀리면 안 되는데 종종 틀리는 것 같다. 조심해야겠다