Simple Python DFS


  • 0
    M
        def countComponents(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: int
            """
            from collections import deque, defaultdict
            
            G = { i: set() for i in xrange(n) }
            for u, v in edges:
                G[u].add(v)
                G[v].add(u)
            
            count = 0
            nums = set(range(n))
            while nums:
                start = nums.pop()
                S = [start]
                visited = set()
                
                while S and nums:
                    num = S.pop()
                    visited.add(num)
                    if num in nums:
                        nums.remove(num)
                    S.extend(G[num] - visited)
                count += 1
            
            return count
    

Log in to reply
 

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