Number of Connected Components in an Undirected Graph

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    You get n nodes labeled 0 to n − 1 and a list of undirected edges. Return the number of connected components: groups of nodes where every node can reach every other node in the group through edges. A node with no edges is a component by itself.

    This is the cleanest union-find question there is, and a common warm-up before harder grouping problems. It can also be solved with BFS or DFS, and interviewers like to hear you compare the two. Original problem: LeetCode 323 (premium).

    Example

    With n = 5 and edges 0-1, 1-2, 3-4, nodes 0, 1 and 2 form one group and 3 and 4 form another, so the answer is 2.
    With n = 5 and edges 0-1, 1-2, 3-4, nodes 0, 1 and 2 form one group and 3 and 4 form another, so the answer is 2.
    Input:  n = 5, edges = [[0, 1], [1, 2], [3, 4]]
    Output: 2
    Input:  n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
    Output: 1
    Input:  n = 4, edges = []
    Output: 4           # every node is its own component

    Constraints (assumed)

    • 1 ≤ n ≤ 2,000.
    • 0 ≤ number of edges ≤ 5,000; no duplicate edges; no self-loops.

    What this question tests

    • Recognizing connected components and choosing between union-find and graph traversal.
    • Implementing union-find correctly: find with path compression, and a union that only counts real merges.
    • Handling isolated nodes and cycles.

    Questions to ask first

    1. Are edges undirected? (Yes. For directed graphs, "connected" needs a different definition.)
    2. Can there be duplicate edges or self-loops? Union-find handles both safely; a counting shortcut does not.
    3. Do all n nodes count, even ones that never appear in an edge? (Yes.)
    4. Will edges arrive over time? If so, union-find is the natural fit because it updates incrementally.