union-find, dfs, bfs


  • 0
    D
    a) union-find
    class Solution(object):
        def validTree(self, n, edges):
            self.group = n
            self.parent = range(n)
            return all(map(self.union, edges)) and self.group == 1
        
        def find(self, k):
            if self.parent[k] != k:
                grand_parent = self.find(self.parent[k])
                self.parent[k] = grand_parent
                return grand_parent
            return k
            
        def union(self, xy):
            x_parent = self.find(xy[0])
            y_parent = self.find(xy[1])
            self.parent[x_parent] = y_parent
            if x_parent != y_parent:
                self.group -= 1
                return True
            return False
    
    b) dfs
    class Solution(object):
        def validTree(self, n, edges):
            adj = collections.defaultdict(set)
            for x, y in edges:
                adj[x].add(y)
                adj[y].add(x)
    
            visited = set()
            if not self.dfs(adj, 0, visited):
                return False
            return all(i in visited for i in range(n))
        
        def dfs(self, adj, idx, visited):
            if idx in visited:
                return False
            visited.add(idx)
            for child in adj[idx]:
                if idx in adj[child]:
                    adj[child].remove(idx)
                if not self.dfs(adj, child, visited):
                    return False
            return True
    
    c) bfs
    class Solution(object):
        def validTree(self, n, edges):
            adj = {i:set() for i in range(n)}
            for x, y in edges:
                adj[x].add(y)
                adj[y].add(x)
                
            visited = set()
            deque = collections.deque([0])
            while deque:
                idx = deque.popleft()
                if idx in visited:
                    return False
                visited.add(idx)
                for child in adj[idx]:
                    if idx in adj[child]:
                        adj[child].remove(idx)
                    deque.append(child)
                adj.pop(idx)
            return not adj

Log in to reply
 

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