문제 출처

1. 문제설명

  • {0}, {1}, {2}, ..., {n}이 있다.
  • 합집합 연산과 두 원소가 같은 집합에 포함되는지 확인하는 연산을 수행하려고 한다.

  • 연산에 대한 결과를 출력하라

  • 문제 분류
    • Disjoint set


2. 알고리즘 설계

  • Union-Find 문제이다.

    • 사실 알고리즘 단톡방에서 문제 추천 받음.

  • 로직
    • 합집합 연산은 부모를 통일시켜주면 되고,
    • 확인하는 연산은 Find를 통해 부모가 같은지 확인해주면 된다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 1'000'002;
int n, m, opt, a, b, P[SZ];

int Find(int u) {
    if(P[u] == u) return u;
    return P[u] = Find(P[u]);
}

void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    P[u] = v;
}

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

    cin >> n >> m;

    for(int i=0; i<=n; i++) P[i] = i;

    while(m--) {
        cin >> opt >> a >> b;

        if(opt == 0) Union(a, b);
        else cout << (Find(a) == Find(b) ? "YES\n": "NO\n");
    }    

    return 0;
}