forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsounmind.py
More file actions
40 lines (29 loc) · 1.16 KB
/
sounmind.py
File metadata and controls
40 lines (29 loc) · 1.16 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
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# If the number of edges is not equal to n-1, it can't be a tree
if len(edges) != n - 1:
return False
# Initialize node_list array where each node is its own parent
node_list = list(range(n))
# Find root function with path compression
def find_root(node):
if node_list[node] != node:
node_list[node] = find_root(node_list[node])
return node_list[node]
def union_and_check_cycle(node1, node2):
root1 = find_root(node1)
root2 = find_root(node2)
if root1 != root2:
node_list[root2] = root1
return True
else:
return False
for node1, node2 in edges:
if not union_and_check_cycle(node1, node2):
return False
return True
# Example usage:
solution = Solution()
print(solution.validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]])) # Output: True
print(solution.validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]])) # Output: False