문제
풀이
유니온 파인드(Union find) 자료구조에 대한 문제이다. union(두 집합을 하나로 합치는 연산), find(원소가 속한 집합을 반환)하는 자료구조이다. find에서는 parent배열을 통하여 부모 노드를 계속해서 재귀함수 호출을 이용하여 찾아내 root가 뭔지를 확인한다. 만약 root가 같다면 그 두 원소는 같은 집합에 속해있다고 말할 수 있다. union(코드에서는 merge)은 find함수를 이용해 root값을 찾아내고, 이미 두 원소가 같은 집합에 있어 root값이 같다면 더 이상 해줄 것이 없어 return을 하고 그렇지 않다면, 트리의 높이를 비교한다. merge를 할 때는 트리의 높이를 작게 유지해야 find함수를 할 때 재귀호출을 덜 하게끔 할 수 있다. 그러므로, ran배열을 통해 트리의 높이를 확인하여 merge를 한다. 만약 트리의 높이가 같은 두 개의 집합을 merge할 때는 트리의 높이 +1을 하여 연산을 계속 진행한다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
using namespace std;
int n, m;
int parent[1000001];
int ran[1000001];
int find(int x){
if(parent[x] < 0) return x;
return parent[x] = find(parent[x]);
}
void merge(int x, int y){
x = find(x);
y = find(y);
// x가 항상 y보다 작게.
if(x == y) return;
if(ran[x] > ran[y]) swap(x, y); // x > y보다 크다면 서로 바꾼다.
parent[x] = y; //높이가 작은 트리를 높이가 높은 곳으로 들어가게끔
if(ran[x] == ran[y]) ran[y]++;
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 0; i<=n; i++){
parent[i] = -1;
ran[i] = 1;
}
for(int i = 0; i<m; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if(a == 0){
merge(b, c);
}
else if(a == 1){
//check
if(find(b) == find(c)){
printf("YES\n");
}
else printf("NO\n");
}
}
}
