집합의 표현 1717

문제

접근 방법

유니온 파인드를 사용하면 풀리는 문제이다. 수의 기준을 잡아 더 큰 수 또는 더 작은 수를 루트로 올리고 다른 집합은 연결해주는 방식을 하면 된다.
집합에 루트를 찾는 과정에선 경로 압축을 해주면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> parents;
int find(int num)
{
    if (parents[num] == num)
        return num;
    return parents[num] = find(parents[num]);
}
void merge(int num1, int num2)
{
    int x = find(num1);
    int y = find(num2);
    if (x < y)
    {
        parents[y] = x;
    }
    else
    {
        parents[x] = y;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, x, a, b;
    cin >> n >> m;
    parents = vector<int>(n + 1);
    for (int i = 1; i <= n; ++i)
        parents[i] = i;
    while (m--)
    {
        cin >> x >> a >> b;
        if (x)
        {
            if (find(a) == find(b))
                cout << "YES";
            else
                cout << "NO";
            cout << "\n";
        }
        else
        {
            merge(a, b);
        }
    }
    return 0;
}

풀이

같은 집합인지 확인해줄 때 자주 사용되는 유니온 파인드를 알아두면 좋다.
유니온 파인드를 오랜만에 구현해봐서 헷갈렸다. 생각보다 자주 보이는 유형인 만큼 유니온 파인드 문제를 많이 풀어봐야겠다.