forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhi-rachel.py
More file actions
42 lines (32 loc) ยท 1 KB
/
hi-rachel.py
File metadata and controls
42 lines (32 loc) ยท 1 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
"""
- ์ ์ ๊ฐ์ n, ๊ฐ์ ๋ฐฐ์ด edges
- ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ
ํธ๋ฆฌ ์กฐ๊ฑด
1. ์์ ํ ์ฐ๊ฒฐ๋ ๊ทธ๋ํ์ฌ์ผ ํจ -> ์ ์ฒด ํ์ ๊ฐ๋ฅ
2. ๊ทธ๋ํ์ ์ํํ๋ ๋ถ๋ถ์ด ์์ด์ผ ํจ
ํธ๋ฆฌ ํน์ฑ์ ํญ์ e = n - 1, ์ฆ ๊ฐ์ ์ ์ = ๋
ธ๋์ ๊ฐ์ - 1
TC: O(n)
SC: O(n)
"""
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
graph = [[] for _ in range(n)]
visited = set()
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
def has_cycle(node, prev):
# ์ด๋ฏธ ๋ฐฉ๋ฌธ = ์ํ -> ํธ๋ฆฌ x
if node in visited:
return True
visited.add(node)
for adj in graph[node]:
if adj == prev:
continue
if has_cycle(adj, node):
return True
return False
if has_cycle(0, -1):
return False
return len(visited) == n