-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathUnion-Find.html
More file actions
53 lines (47 loc) · 1.9 KB
/
Union-Find.html
File metadata and controls
53 lines (47 loc) · 1.9 KB
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
53
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
// Union-Find - 합집합 찾기, 여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 이 두 노드가
// 서로 같은 그래프에 속하는지 판별하는 알고리즘
function getParent(parent, x) { // 재귀함수로, 해당 수의 부모를 찾습니다
if(parent[x] === x) return x; // 인덱스와 인덱스속 값이 서로 같을때 -> 부모
return parent[x] = getParent(parent, parent[x]); // 재귀가 끝나고 싹다 부모값으로 바뀝니다.
}
function unionParent(parent, a, b) { // if) a = 2, b = 8
a = getParent(parent, a); // a = 1
b = getParent(parent, b); // b = 5
if(a < b) parent[b] = a;
// b가 원래 자기값을 가지는 다른 그래프의 부모였는데,
// b안의 값을 a로 바꿔서 b의 부모를 자기자신이 아닌 a로 바꿨음
else parent[a] = b;
}
function findParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
if(a === b) return 1;
return 0;
}
let parent = [0];
for(let i = 1; i <= 10; i++) {
parent.push(i);
}
unionParent(parent, 1, 2);
unionParent(parent, 2, 3);
unionParent(parent, 3, 4);
unionParent(parent, 5, 6);
unionParent(parent, 6, 7);
unionParent(parent, 7, 8);
console.log(parent);
// case 1) unionParent(parent, 1, 5);
// case 2) unionParent(parent, 2, 8);
console.log(findParent(parent, 1, 5));
</script>
</body>
</html>