AlgoMaster Logo

Number of Connected Components in an Undirected Graph

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We're given an undirected graph with n nodes (labeled 0 to n-1) and a list of edges. We need to count how many separate groups of connected nodes exist. Two nodes are in the same component if you can reach one from the other by following edges.

A component is a maximal set of nodes that are all reachable from each other. If you start at any node and follow edges as far as you can, you cover exactly one component. The answer is the number of distinct sets you would cover if you repeated that from every node.

This is a graph connectivity problem. Two families of solutions apply: traverse the graph (DFS or BFS) and count how many separate traversals it takes to reach every node, or use Union Find to merge connected nodes and count the groups that remain.

Key Constraints:

  • 1 <= n <= 2000 -> The node count is small, so both an O(V + E) traversal and a near-linear Union Find run comfortably within limits.
  • 1 <= edges.length <= 5000 -> The graph is sparse. An adjacency list costs O(V + E) space, which is at most a few thousand entries.
  • 0 <= ai <= bi < n -> Nodes are zero-indexed and there are no self-loops, so every edge connects two distinct valid nodes.

Approach 1: DFS

Intuition

A single DFS started from a node visits every node in that node's component and nothing outside it. So we can count components by counting how many times we have to start a fresh DFS. Walk through the nodes in order. When we hit one that has not been visited yet, it belongs to a component we have not seen, so we increment the count and run DFS to mark the whole component as visited. The next unvisited node we reach must start a new component.

Algorithm

  1. Build an adjacency list from the edges array.
  2. Create a visited boolean array of size n.
  3. Initialize a components counter to 0.
  4. For each node from 0 to n-1:
    • If the node hasn't been visited, increment components and run DFS from that node.
    • The DFS marks all reachable nodes as visited.
  5. Return components.

Visualization and Code

Loading animation...

The traversal approach builds an adjacency list and explores the graph. The next approach takes a different route: it processes edges directly and merges groups as it goes, without ever building an adjacency list.

Approach 2: Union Find

Intuition

Union Find counts components without traversing the graph. Start by treating every node as its own component, so the count begins at n. Process the edges one by one. Each edge connects two nodes; if those nodes are in different components, merge the two components and decrement the count. If they are already in the same component, the edge changes nothing. After all edges are processed, the count is the number of components.

Union Find tracks groups with a parent pointer per node. Initially every node points to itself and is its own root. To merge two nodes, point one root at the other. Two refinements keep operations near O(1): path compression flattens the tree during a find by repointing every node on the path directly to the root, and union by rank attaches the shorter tree under the taller one so the tree stays shallow.

Algorithm

  1. Initialize a parent array where parent[i] = i (each node is its own root).
  2. Initialize a rank array of zeros (for union by rank).
  3. Set components = n (initially, every node is a separate component).
  4. For each edge [a, b]:
    • Find the root of a and the root of b.
    • If they have different roots, union them and decrement components.
  5. Return components.

Visualization and Code

Loading animation...