Python bfs solution, O(edge + node) complexity

  • 0
    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:
            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:
            return counter

Log in to reply

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