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

쉬운 목차

질문

라인 1717: 집합 표현

처음에는 $n+1$ 세트 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$가 있습니다. 여기서는 합집합 연산과 두 요소가 같은 집합에 포함되어 있는지 확인하는 연산을 수행하려고 합니다.컬렉션을 나타내는 프로그램 작성

www.acmicpc.net

설명하다

‘0 a b’가 주어지면 집합 a와 b를 병합합니다. ‘1 a b’가 주어지면 a와 b가 같은 집합인지 확인합니다.

Union Find를 수행할 수 있으며 아래 블로그에 자세히 설명되어 있습니다.

한 줄 한 줄 천천히 읽으면 바로 이해할 수 있습니다.

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

(알고리즘) 합집합 조회

Union-Find ① Union-Find란? ▷ 그래프 알고리즘의 대표로 “합집합”을 의미합니다. ▷ Disjoint-set이라고도 합니다. ▷ 다중 노드 존재

www.brenden.

#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;
}