# A python solution with topological-sort

• This solution looks like topological-sort, which iteratively removes the nodes with degree of 1.
The base condition is that a single node with no edges is a tree. By induction, if the graph is a tree, with the leaves removed, the rest part of it is still a tree.

``````class Solution:
# @param {integer} n
# @param {integer[][]} edges
# @return {boolean}
def validTree(self, n, edges):
graph = {i:set() for i in xrange(n)}
for p, q in edges:
while len(graph) > 0:
leaves = list()
for node, neighbors in graph.iteritems():
if len(neighbors) <= 1:
leaves.append(node)
if len(leaves) == 0:
return False # a cycle exists
for n in leaves:
if len(graph[n]) == 0:
# must be one connected component
return len(graph) == 1
nei = graph[n].pop()
graph[nei].remove(n)
del graph[n]
return True``````

• Great solution by using topological sort here!

• @clockwise9 A great example to topologically sort a undirected graph. For directed graph, we always start with nodes with 0 in-degree. For undirected graph, we first turn every undirected edge into two directed edges, and then start with nodes with 1 in-degree, or out-degree.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.