Number of Connected Components in Undirected Graph

Graph
Medium

Approach

Diagrams

Analysis

Time

Space

from collections import deque


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

        for node in range(n):
            if node in visited:
                continue
            self.bfs(node, graph, visited)
            count += 1

        return count

    def buildGraph(self, n, edges):
        graph = {i: set() for i in range(n)}

        for node, otherNode in edges:
            graph[node].add(otherNode)
            graph[otherNode].add(node)

        return graph

    def bfs(self, node, graph, visited):
        queue = deque([node])

        while queue:
            cur = queue.popleft()
            neighbors = graph[cur]
            for neighbor in neighbors:
                if neighbor in visited:
                    continue
                queue.append(neighbor)
                visited.add(neighbor)

Learn

#Breadth-First Search

Videos