(백준) 1717 - 집합 표현(C++)

쉬운 목차

문제

라인 1717: 수량 표현

처음에는 $n+1$ 세트 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$가 있습니다. 여기서 우리는 합집합 연산과 두 요소가 같은 집합에 있는지 확인하는 연산을 수행하려고 합니다. 집합을 표시하는 프로그램을 작성하십시오.

www.acmicpc.net

설명

‘0 ab’에서 집합 a와 b를 병합합니다. ‘1 ab’이면 a와 b가 동일한 집합인지 확인합니다.

다음 블로그에서 자세히 설명하는 Union Find를 할 수 있습니다.

한 줄 한 줄 천천히 읽으면 금방 이해가 됩니다.

(알고리즘) Union-Find – Brandon의 패션 블로그(tistory.com)

(알고리즘) 합집합 찾기

유니온파인드 ① 유니온파인드란? ▷ 대표적인 그래프 알고리즘으로 합집합을 찾는다는 의미 ▷ disjoint set이라고도 함 ▷ 노드가 여러 개 있음

brenden.tistory.com

#include <iostream>
using namespace std;
int parent(1000001);

int find(int x) {
    return parent(x) == x ? x : parent(x) = find(parent(x));
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) 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 = 1; i < 1000001; i++) {
        parent(i) = i;
    }

    for (int i = 0; i < m; i++) {
        int q, a, b;
        cin >> q >> a >> b;

        if (q == 0) {
            merge(a, b);
        } else {
            if (find(a) == find(b)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}