forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhwanmini.js
More file actions
45 lines (35 loc) ยท 1.06 KB
/
hwanmini.js
File metadata and controls
45 lines (35 loc) ยท 1.06 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
// V: Node ๊ฐ์, E: ๊ฐ์ ์ ๊ฐ์
// ์๊ฐ๋ณต์ก๋: O(V + E)
// ๊ณต๊ฐ๋ณต์ก๋: O(V + E)
class Solution {
/**
* @param {number} n
* @param {number[][]} edges
* @returns {boolean}
*/
validTree(n, edges) {
const graph = new Map();
for (let [u, v] of edges) {
if (!graph.has(u)) graph.set(u, [])
if (!graph.has(v)) graph.set(v, [])
graph.get(u).push(v)
graph.get(v).push(u)
}
const visited = Array.from({length: n}, () => false);
let edgeCount = 0;
const queue = [0];
visited[0] = true
while(queue.length) {
const cur = queue.shift();
for (const edge of graph.get(cur) || []) {
if (!visited[edge]) {
visited[edge] = true;
queue.push(edge)
}
edgeCount++;
}
}
const isAllVisited = visited.every((visited) => visited === true)
return isAllVisited && (edgeCount / 2) === (n - 1)
}
}