LeetCode 323: Number Of Connected Components In An Undirected Graph — Step-by-Step Visual Trace

Medium — Graph | Depth-First Search | Union Find | Connected Components

The Problem

Given n nodes labeled from 0 to n-1 and a list of undirected edges, return the number of connected components in the graph.

Approach

Build an adjacency list representation of the graph, then use depth-first search (DFS) to traverse each unvisited component. For each unvisited node, perform DFS to mark all nodes in that component as visited and increment the component counter.

Time: O(V + E) · Space: O(V + E)

Code

from collections import defaultdict, deque

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        visited = set()
        components = 0

        for node in range(n):
            if node not in visited:
                components += 1
                dfs(node)

        return components

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments