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

쉬운 목차

질문

1717: 세트 표기법(acmicpc.net)

라인 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; }