0261-graph-valid-tree.py

# Problem is free on Lintcode
classSolution:
"""
 @param n: An integer
 @param edges: a list of undirected edges
 @return: true if it's a valid tree, or false
 """

defvalidTree(self, n, edges):
ifnotn:
returnTrue
adj= {i: [] foriinrange(n)}
forn1, n2inedges:
adj[n1].append(n2)
adj[n2].append(n1)

visit=set()

defdfs(i, prev):
ifiinvisit:
returnFalse

visit.add(i)
forjinadj[i]:
ifj==prev:
continue
ifnotdfs(j, i):
returnFalse
returnTrue

returndfs(0, -1) andn==len(visit)



# alternative solution via DSU O(ElogV) time complexity and 
# save some space as we don't recreate graph\tree into adjacency list prior dfs and loop over the edge list directly
classSolution:
"""
 @param n: An integer
 @param edges: a list of undirected edges
 @return: true if it's a valid tree, or false
 """
def__find(self, n: int) ->int:
whilen!=self.parents.get(n, n):
n=self.parents.get(n, n)
returnn

def__connect(self, n: int, m: int) ->None:
pn=self.__find(n)
pm=self.__find(m)
ifpn==pm:
return
ifself.heights.get(pn, 1) >self.heights.get(pm, 1):
self.parents[pn] =pm
else:
self.parents[pm] =pn
self.heights[pm] =self.heights.get(pn, 1) +1
self.components-=1

defvalid_tree(self, n: int, edges: List[List[int]]) ->bool:
# init here as not sure that ctor will be re-invoked in different tests
self.parents= {}
self.heights= {}
self.components=n

fore1, e2inedges:
ifself.__find(e1) ==self.__find(e2): # 'redundant' edge
returnFalse
self.__connect(e1, e2)

returnself.components==1# forest contains one tree