Python bfs solution, O(edge + node) complexity


  • 0
    Y
    class Solution(object):
        def countComponents(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: int
            """
            connected = collections.defaultdict(set)
            for e in edges:
                connected[e[0]].add(e[1])
                connected[e[1]].add(e[0])
            
            visited = {}
            counter = 0
            
            for i in xrange(n):
                if i not in visited:
                    counter += 1
                    q = collections.deque([i])
                    while q:
                        cur = q.popleft()
                        visited[cur] = True
                        for each in connected[cur]:
                            if each not in visited:
                                q.append(each)
            
            return counter
    

Log in to reply
 

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