LintCode Q178 Graph Valid Tree in Python

  • Jinhai ZHOU
  • 7 Minutes
  • 2016年11月3日
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
class Solution:
# @param {int} n an integer
# @param {int[][]} edges a list of undirected edges
# @return {boolean} true if it's a valid tree, or false
def validTree(self, n, edges):
# Write your code here
class UnionFind(object):
def __init__(self, n):
self._tree = [i for i in xrange(n)]
self._size = [1 for i in xrange(n)]
# weighted tree
def union(self, p, q):
if p == q:
return
p = self.root(p)
q = self.root(q)
if self._size[p] >= self._size[q]:
self._tree[q] = p
self._size[p] += 1
else:
self._tree[p] = q
self._size[q] += 1
# path compression
def root(self, i):
while(self._tree[i] != i):
self._tree[i] = self._tree[self._tree[i]]
i = self._tree[i]
return i
def find(self, p, q):
p_root = self.root(p)
q_root = self.root(q)
if p_root == q_root:
return True
else:
return False
if len(edges) != n - 1:
return False
union_find = UnionFind(n)
all_connected = False
for [p, q] in edges:
if union_find.find(p, q):
return False
else:
union_find.union(p, q)
return len(edges) == n - 1
# Weighted quick-union with path compression WQUPC
# worst case time complexity O(N+Mlg*N)
# where N is data length, M is union-find ops times
# in theory, WQUPC is not quite linear
# in practice, WQUPC is linear
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。