323. Number of Connected Components in an Undirected Graph

[tech-cow]

323. Number of Connected Components in an Undirected Graph

Buggy

class Solution(object):
    def countComponents(self, n, edges):
        graph = self.makeGraph(edges)
        count = 0
        for i in range(n):
            if i in graph: continue    # wtf? if i in visited
            self.bfs(graph, i)
            count += 1
        return count
    
    
    def makeGraph(self, edges):
        graph = collections.defaultdict(list)
        for n1, n2 in edges:
            graph[n1].append(n2)
            graph[n2].append(n1)
        return graph

    
    def bfs(self, graph, index):
        queue, visited = collections.deque([index]), set(index)  # visited needs to be outside/global
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

Final Solution

class Solution(object):
    def countComponents(self, n, edges):
        graph = self.makeGraph(edges)
        count = 0
        visited = set()        

        for i in range(n):    
            if i in visited: continue
            self.bfs(graph, i, visited)
            count += 1
        return count
    
    
    def makeGraph(self, edges):
        graph = collections.defaultdict(list)
        for n1, n2 in edges:
            graph[n1].append(n2)
            graph[n2].append(n1)
        return graph

    
    def bfs(self, graph, index, visited):
        queue = collections.deque([index])
        while queue:
            node = queue.popleft()
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)