Domain 2MediumCORE

Number of Connected Components in an Undirected Graph

We are given an undirected graph with $n$ labeled vertices ($0$ to $n-1$) and a list of edges connecting them. The goal is to determine how many disjoint sets (connected components) exist in the entire structure.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search#Union Find#Graph

323. Number of Connected Components in an Undirected Graph

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search,Union Find,Graph
FAANG asked: 1
Acceptance rate: 58.2%


Problem Breakdown

We are given an undirected graph with nn labeled vertices (00 to n−1n-1) and a list of edges connecting them. The goal is to determine how many disjoint sets (connected components) exist in the entire structure.

Key Inputs:

  • n: Total number of nodes.
  • edges: List of pairs [u, v] representing undirected connections.

Implicit Constraints & Edge Cases:

  1. Isolated Nodes: A node might not appear in any edge list (e.g., N=5N=5, edges only connect {0,1}\{0,1\} and {3,4}\{3,4\}). This node (22) forms its own component. Our logic must account for nodes that never get merged into a larger set.
  2. Empty Edges: If edges is empty or N=1N=1, every node is isolated; the answer should be nn.
  3. Disconnected Graphs: The graph might not form a single tree but multiple disjoint subgraphs (like Example 1).

Intuition

Initially, we can assume that without any edges provided in edges, every node exists as its own separate component. Therefore, the starting count of connected components is nn.

As we iterate through each edge [u, v]:

  • If nodes u and v are already part of the same connected group (i.e., they share a root in our data structure), adding this edge doesn’t change the number of components. We simply ignore it because redundancy is allowed but unnecessary for connectivity counting.
  • If u and v belong to different groups, connecting them merges these two distinct sets into one single component. This operation reduces the total count of connected components by exactly 1.

This logic suggests we need a data structure that efficiently tracks which nodes are in the same group and allows us to merge those groups quickly. A Disjoint Set Union (DSU) or Union-Find structure is ideal for this because it supports find (check if two elements share a root) and union (merge sets) operations nearly instantly (O(α(N))O(\alpha(N))).

Alternatively, we could build an adjacency list and run BFS/DFS from every unvisited node. While valid, DSU avoids the overhead of building explicit graph structures when only connectivity counts are needed. I will proceed with Union-Find for its efficiency in this specific counting problem.

Approach

  1. Initialize: Create a parent array where each index points to itself (parent[i] = i). This represents nn initial components. Initialize a variable num_components to nn.
  2. Iterate Edges: Loop through every [u, v] in the input list.
  3. Find Roots: For both nodes u and v, find their representative root using path compression (to keep tree height low).
  4. Union Logic:
    • If root_u != root_v: Perform a union operation (make one parent point to the other, optionally by rank/size for balance) and decrement num_components.
    • If root_u == root_v: They are already connected; do nothing.
  5. Return: After processing all edges, return num_components.

Complexity Analysis

  • Time Complexity: O(E⋅α(N))O(E \cdot \alpha(N)), where EE is the number of edges and α\alpha is the inverse Ackermann function (effectively constant). Initialization takes O(N)O(N). In practice, this simplifies to nearly linear time relative to input size.
  • Space Complexity: O(N)O(N) for storing the parent array (and optionally a rank or size array if used for union optimization).

Solution

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        # Optional rank/size arrays could be added here to ensure O(log N) height. 
        # For this problem constraints (N <= 2000), simple path compression is sufficient.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        
        for u, v in edges:
            root_u = self._find(uf.parent, u)
            root_v = self._find(uf.parent, v)
            
            if root_u != root_v:
                # Merge the two sets. 
                # We attach one tree to another arbitrarily here (path compression handles balance).
                uf.parent[root_u] = root_v
                
        return n - len(edges)  # Wait, this logic is flawed in thought process above?
                              # No, decrementing a counter inside loop is safer than math at end.

    def _find(self, parent, x):
        path_compression: 
            if parent[x] != x:
                parent[x] = self._find(parent, parent[x])
            return parent[x]

Correction on Code Logic: The previous snippet had a logic error in the thought block. I need to write clean code that decrements count or returns initial NN minus successful unions.

Revised Solution Plan: Initialize count = n. Inside loop, if roots differ: union and decrement count. Return count. I will implement iterative find for robustness against recursion limits in Python (default 1000), though path compression usually mitigates depth issues quickly enough. I’ll stick to recursive with memoization logic or just standard implementation which is accepted on LeetCode for N=2000. To be safe and “Senior”, I will use iterative find inside the solution block to avoid RecursionError risks entirely, even if unlikely here.

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        
        # Iterative Find with Path Compression
        def find(i):
            root = i
            while root != parent[root]:
                root = parent[root]
            
            # Compress path from current node to root
            curr = i
            while curr != root:
                nxt = parent[curr]
                parent[curr] = root
                curr = nxt
            return root
        
        components = n
        
        for u, v in edges:
            root_u = find(u)
            root_v = find(v)
            
            if root_u != root_v:
                # Union by attaching one to another arbitrarily 
                parent[root_u] = root_v
                components -= 1
                
        return components

Edge Cases Handled

  • Isolated Nodes: If a node never appears in edges, its parent remains itself. It is counted as an initial component and never merged, correctly contributing to the final count.
  • Empty Edges List: The loop over edges does not execute; function returns initialized n (correct).
  • Single Node (N=1N=1): Returns 1 regardless of edge list content (though constraints say 0≤ai<n0 \le a_i < n, so valid indices exist).