(백준) 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;
}