-
Notifications
You must be signed in to change notification settings - Fork 17
/
graph-valid-tree.py
36 lines (28 loc) · 1.03 KB
/
graph-valid-tree.py
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
from typing import List
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def find(array: List[int], pos: int):
root = pos
while root != array[root]:
root = array[root]
while pos != root:
array[pos], pos = root, array[pos]
return root
def union(root_left: int, root_right: int, array: List[int], count: List[int]):
root_less, root_more = sorted(
(root_left, root_right), key=lambda x: count[x]
)
array[root_less] = root_more
count[root_more] += count[root_less]
array = list(range(n))
count = [1] * n
groups = n
for left, right in edges:
root_left = find(array, left)
root_right = find(array, right)
if root_left == root_right:
return False
else:
union(root_left, root_right, array, count)
groups -= 1
return groups == 1