loading

Number of Connected Components — Step-by-Step Visualization

mediumLeetCode #323GraphDFSBFSUnion Find

You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [a_i, b_i]` indicates that there is an edge between `a_i` and `b_i` in the graph. Return the number of connected components in the graph.

Algorithm Pattern

Graph Traversal (DFS/BFS)

Key Idea

A connected component is a maximal set of nodes where any two nodes are reachable from each other. We can count components by iterating through all nodes. For each unvisited node, we start a DFS/BFS to mark all reachable nodes as visited. Each time we start a traversal from an unvisited node, we've found a new connected component.

Step-by-Step Approach

  1. Build an adjacency list from the given edges.
  2. Initialize a `visited` set to track visited nodes.
  3. Initialize `count = 0`.
  4. For each node `i` from 0 to `n - 1`:
  5. If `i` is not in `visited`:
  6. Increment `count`.
  7. Start a DFS/BFS from node `i` to mark all connected nodes as visited.
  8. Return `count`.

Common Gotchas

  • Ensure all nodes (even isolated ones) are considered.
  • Handle the undirected nature of edges (add `u -> v` and `v -> u`).

Related Problems

← All problems