forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.js
More file actions
51 lines (46 loc) · 1.16 KB
/
yolophg.js
File metadata and controls
51 lines (46 loc) · 1.16 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
// Time Complexity: O(n)
// Space Complexity: O(n)
class Solution {
validTree(n, edges) {
// initialize Union-Find data structure
const parent = Array(n)
.fill(0)
.map((_, index) => index);
const rank = Array(n).fill(1);
// find function with path compression
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// union function with union by rank
function union(x, y) {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX] += 1;
}
} else {
// if rootX == rootY, there is a cycle
return false;
}
return true;
}
// process each edge
for (const [u, v] of edges) {
if (!union(u, v)) {
// if union returns false, a cycle is detected
return false;
}
}
// if all unions are successful, it's a valid tree
return true;
}
}