A python solution with topological-sort


  • 3
    C

    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:
            graph[p].add(q)
            graph[q].add(p)
        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

  • 0
    C

    Great solution by using topological sort here!


  • 1
    D

    @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.


Log in to reply
 

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