forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.py
More file actions
30 lines (25 loc) · 1 KB
/
yolophg.py
File metadata and controls
30 lines (25 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
# Time Complexity: O(N) - iterate through all edges and nodes at most once.
# Space Complexity: O(N) - store the graph as an adjacency list and track visited nodes.
class Solution:
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
# a tree with 'n' nodes must have exactly 'n-1' edges
if len(edges) != n - 1:
return False
# build an adjacency list (graph representation)
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# use BFS to check if the graph is fully connected and acyclic
visited = set()
queue = [0]
visited.add(0)
while queue:
node = queue.pop(0)
for neighbor in graph[node]:
if neighbor in visited:
continue
visited.add(neighbor)
queue.append(neighbor)
# if we visited all nodes, it's a valid tree
return len(visited) == n