Python in DFS (recursive)


  • 0
    A
    def validTree(self, n, edges):
        self.edge = [[] for i in xrange(n)]
        for e in edges:
            s, d = e
            self.edge[s].append(d)
            self.edge[d].append(s)
        
        self.circle = False
        self.visit = [0] * n
        self.dfs(None, 0) # start from 0
        
        if self.circle or 0 in self.visit:
            return False
        return True
    
    def dfs(self, previous, s):
        if self.circle:
            return
        if self.visit[s] == 2:
            return
        if self.visit[s] == 1:
            self.circle = True
            return
        self.visit[s] = 1
        for d in self.edge[s]:
            if d != previous:
                self.dfs(s, d)
        self.visit[s] = 2

Log in to reply
 

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