forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsungjinwi.py
More file actions
56 lines (43 loc) ยท 1.69 KB
/
sungjinwi.py
File metadata and controls
56 lines (43 loc) ยท 1.69 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
54
55
56
"""
ํ์ด :
valid tree๋ฅผ ๋ง์กฑํ๋ ค๋ฉด ๋ ๊ฐ์ง ์กฐ๊ฑด์ด ํ์ํ๋ค
1. ์ํ์ด ์์ด์ผ ํ๋ค
2. ๋ชจ๋ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋์ด ์์ด์ผํ๋ค
์ด ์กฐ๊ฑด์ ๋ง์กฑํ๋ ค๋ฉด (vertex ์ - 1) == edge ์ ๊ฐ ํ์์กฐ๊ฑด์ด๋ค
edge ์๊ฐ ๋ ์ ๋ค๋ฉด ๋ชจ๋ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋์ง ์๊ณ ๋ ๋ง๋ค๋ฉด ํ์ฐ์ ์ผ๋ก ์ํ์ด ์กด์ฌํ๊ธฐ ๋๋ฌธ
์ ์กฐ๊ฑด์ผ๋ก ํํฐ๋งํ๊ณ ๋์ ๋ชจ๋ ๋
ธ๋๊ฐ ์ฐ๊ฒฐ๋๋์ง์ง ํ์ธํ๋ฉด valid tree๋ฅผ ์ ์ ์๋ค
์ฆ, ์ํ์ ๊ฐ์ง๊ณ ์๋์ง ํ์ธํ๋ ๊ณผ์ ์ด ์๋ต๋๋ค
- edges๋ฅผ ๊ธฐ๋ฐ์ผ๋ก graph๋ฅผ ๋ง๋ ๋ค
๋
ธ๋ ๊ฐ์: N, ๊ฐ์ ๊ฐ์: E
E == N - 1์ ๋จผ์ ํ์ธํ๊ธฐ ๋๋ฌธ์ E๋ N์ ๋น๋กํ๋ค
๋ฐ๋ผ์ N๋ง ์ฌ์ฉ
TC: O(N)
๋ชจ๋ node์ ๋ํด dfsํธ์ถ, edges์ ๋ํ ์ํ๋ node์์ ๋น๋ก
SC: O(N)
dfs ํธ์ถ ์คํ ๋ฐ graph๋ node ์์ ๋น๋ก
"""
from typing import (
List,
)
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
# write your code here
if n - 1 != len(edges) :
return False
graph = [[] for _ in range(n)]
for node, adjcent in edges:
graph[node].append(adjcent)
graph[adjcent].append(node)
visited = set()
def dfs(node):
visited.add(node)
for adj in graph[node]:
if adj not in visited:
dfs(adj)
dfs(0)
return len(visited) == n