forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbhyun-kim.py
More file actions
52 lines (40 loc) · 1.43 KB
/
bhyun-kim.py
File metadata and controls
52 lines (40 loc) · 1.43 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
"""
261. Graph Valid Tree
https://leetcode.com/problems/graph-valid-tree/
Solution:
To solve this problem, we can use the depth-first search (DFS) algorithm.
We can create an adjacency list to represent the graph.
Then, we can perform a DFS starting from node 0 to check if all nodes are visited.
If all nodes are visited, we return True; otherwise, we return False.
Time complexity: O(n)
- We visit each node once.
- The DFS has a time complexity of O(n).
Space complexity: O(n)
- We use an adjacency list to store the graph.
- The space complexity is O(n) for the adjacency list.
"""
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
# Initialize adjacency list
graph = {i: [] for i in range(n)}
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# Function to perform DFS
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor == parent:
continue
if neighbor in visited or not dfs(neighbor, node):
return False
return True
visited = set()
# Start DFS from node 0
if not dfs(0, -1):
return False
# Check if all nodes are visited
return len(visited) == n