Number of Connected Components in an Undirected Graph

Description

You are given an integer n representing the number of nodes in an undirected graph. The nodes are labeled from 0 to n - 1. You are also given a list of edges, where each edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i.

Return the number of connected components in the graph.

A connected component is a maximal set of nodes such that there is a path between every pair of nodes in the set. Two nodes belong to the same connected component if and only if there is a path connecting them through the edges. Nodes that have no path between them belong to different connected components.

Graph with 5 nodes showing two connected components: {0, 1, 2} and {3, 4}

Examples

Example 1

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]

Output: 2

Explanation: The graph has 5 nodes (0 through 4). Edges connect 0–1, 1–2, and 3–4. Nodes 0, 1, and 2 are all reachable from each other (0→1→2), forming one connected component. Nodes 3 and 4 are connected to each other but not to any of 0, 1, 2, forming a second component. There is no way to travel from any node in {0, 1, 2} to any node in {3, 4}. Therefore, the answer is 2.

Example 2

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]

Output: 1

Explanation: Every node is reachable from every other node through the chain of edges: 0–1–2–3–4. All 5 nodes form a single connected component, so the answer is 1.

Example 3

Input: n = 4, edges = []

Output: 4

Explanation: There are no edges at all. Each node is isolated — it cannot reach any other node. Every individual node is its own connected component, giving us 4 components total.

Constraints

1 ≤ n ≤ 2000
0 ≤ edges.length ≤ 5000
edges[i].length == 2
0 ≤ a_i, b_i < n
a_i ≠ b_i
There are no repeated edges

Editorial

Brute Force

Intuition

The most direct way to count connected components is to explore the graph node by node. Start at any unvisited node, then visit every node reachable from it — this gives you one complete connected component. Mark all those nodes as visited. Then find the next unvisited node and repeat the process. Each time you start a new exploration from an unvisited node, you have discovered a new connected component.

This is essentially a Depth-First Search (DFS) approach. Think of it like exploring rooms in a building. You enter through one door, explore every room you can reach through internal doors, and mark each room as explored. Once you run out of rooms to explore, you go outside and look for a completely separate building (another unvisited node). The number of separate buildings you find equals the number of connected components.

DFS uses the call stack (recursion) to remember which nodes to backtrack to, naturally exploring as deep as possible before retreating.

Step-by-Step Explanation

Let's trace with n = 5, edges = [[0, 1], [1, 2], [3, 4]]:

Step 1: Build adjacency list. Node 0: [1]. Node 1: [0, 2]. Node 2: [1]. Node 3: [4]. Node 4: [3].

Step 2: Initialize visited = [false, false, false, false, false]. Components count = 0.

Step 3: Check node 0: not visited. Start DFS from node 0. Increment components to 1.

Step 4: DFS at node 0: mark visited[0] = true. Explore neighbor 1.

Step 5: DFS at node 1: mark visited[1] = true. Explore neighbor 0 (already visited, skip). Explore neighbor 2.

Step 6: DFS at node 2: mark visited[2] = true. Explore neighbor 1 (already visited, skip). No more neighbors. Backtrack.

Step 7: Backtrack to node 1, then to node 0. DFS from node 0 is complete. Component 1 = {0, 1, 2}.

Step 8: Check node 1: visited. Check node 2: visited. Check node 3: not visited. Start DFS from node 3. Increment components to 2.

Step 9: DFS at node 3: mark visited[3] = true. Explore neighbor 4.

Step 10: DFS at node 4: mark visited[4] = true. Explore neighbor 3 (already visited, skip). No more neighbors. Backtrack.

Step 11: DFS from node 3 complete. Component 2 = {3, 4}.

Step 12: Check node 4: visited. All nodes checked. Final answer: 2 components.

DFS — Exploring Connected Components — Watch how DFS explores all reachable nodes from a starting point, marking them as visited. Each new DFS start from an unvisited node discovers a new component.

Algorithm

Build an adjacency list from the edge list.
Create a visited array of size n, initialized to false.
Initialize components = 0.
For each node i from 0 to n-1:
- If visited[i] is false:
  - Increment components.
  - Run DFS from node i, marking all reachable nodes as visited.
Return components.

Code

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        vector<bool> visited(n, false);
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                dfs(adj, visited, i);
            }
        }
        return components;
    }
    
    void dfs(vector<vector<int>>& adj, vector<bool>& visited, int node) {
        visited[node] = true;
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                dfs(adj, visited, neighbor);
            }
        }
    }
};

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        visited = [False] * n
        components = 0
        
        def dfs(node):
            visited[node] = True
            for neighbor in adj[node]:
                if not visited[neighbor]:
                    dfs(neighbor)
        
        for i in range(n):
            if not visited[i]:
                components += 1
                dfs(i)
        
        return components

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                dfs(adj, visited, i);
            }
        }
        return components;
    }
    
    private void dfs(List<List<Integer>> adj, boolean[] visited, int node) {
        visited[node] = true;
        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(adj, visited, neighbor);
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Building the adjacency list takes O(E). The DFS visits each node exactly once (due to the visited check) and traverses each edge exactly twice (once from each endpoint). Total: O(V + E). With V ≤ 2000 and E ≤ 5000, this is very fast.

Space Complexity: O(V + E)

The adjacency list stores 2E entries (each undirected edge appears twice). The visited array takes O(V). The recursion stack can go up to O(V) deep in the worst case (a path graph). Total: O(V + E).

Why This Approach Is Not Efficient

The DFS approach is already O(V + E) in time, which is asymptotically optimal for this problem — you must examine every node and every edge at least once. However, it has a practical limitation: recursion depth.

If the graph is a single long chain (e.g., 0–1–2–...–1999), the DFS recursion goes 2000 levels deep. In languages with limited stack sizes (like Python's default recursion limit of ~1000), this causes a stack overflow. An iterative BFS approach or a stack-based iterative DFS avoids this issue.

Additionally, the DFS/BFS approach requires building a full adjacency list first (O(V + E) space). For certain graph processing scenarios, the Union-Find (Disjoint Set Union) approach can process edges as they arrive without needing the full adjacency list, and it avoids recursion entirely.

Better Approach - Breadth-First Search (BFS)

Intuition

Instead of exploring as deep as possible (DFS), we can explore level by level using a queue. BFS starts from a node, visits all its direct neighbors first, then visits their neighbors, and so on — like ripples spreading outward from a stone dropped in water.

The logic for counting components is the same: iterate through all nodes, and whenever you find an unvisited node, start a BFS from it (that's one new component) and mark everything reachable as visited.

The key advantage of BFS over recursive DFS is that BFS uses an explicit queue instead of the call stack, avoiding stack overflow issues with large graphs. Both have the same asymptotic complexity, but BFS is more robust for deep or chain-like graphs.

Step-by-Step Explanation

Let's trace with n = 5, edges = [[0, 1], [1, 2], [3, 4]]:

Step 1: Build adjacency list. Same as before.

Step 2: Initialize visited = [F, F, F, F, F], components = 0.

Step 3: Node 0 is unvisited. Increment components to 1. Enqueue node 0, mark visited[0] = true. Queue: [0].

Step 4: Dequeue 0. Process neighbors: neighbor 1 is unvisited → mark visited[1] = true, enqueue 1. Queue: [1].

Step 5: Dequeue 1. Process neighbors: neighbor 0 (visited, skip). Neighbor 2 is unvisited → mark visited[2] = true, enqueue 2. Queue: [2].

Step 6: Dequeue 2. Process neighbors: neighbor 1 (visited, skip). Queue is now empty. BFS complete. Component 1 = {0, 1, 2}.

Step 7: Nodes 1, 2 are visited. Node 3 is unvisited. Increment components to 2. Enqueue 3, mark visited[3] = true. Queue: [3].

Step 8: Dequeue 3. Neighbor 4 is unvisited → mark visited[4] = true, enqueue 4. Queue: [4].

Step 9: Dequeue 4. Neighbor 3 (visited, skip). Queue empty. BFS complete. Component 2 = {3, 4}.

Step 10: Node 4 visited. All nodes processed. Answer: 2.

BFS — Level-by-Level Component Discovery — Watch how BFS uses a queue to explore all nodes reachable from a starting point, processing neighbors level by level before moving to the next component.

Algorithm

Build an adjacency list from the edge list.
Create a visited array of size n, initialized to false.
Initialize components = 0.
For each node i from 0 to n-1:
- If visited[i] is false:
  - Increment components.
  - Create a queue, enqueue i, and mark visited[i] = true.
  - While the queue is not empty:
    - Dequeue a node curr.
    - For each neighbor of curr:
      - If the neighbor is not visited, mark it visited and enqueue it.
Return components.

Code

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int>> adj(n);
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        vector<bool> visited(n, false);
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                queue<int> q;
                q.push(i);
                visited[i] = true;
                while (!q.empty()) {
                    int curr = q.front();
                    q.pop();
                    for (int neighbor : adj[curr]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            q.push(neighbor);
                        }
                    }
                }
            }
        }
        return components;
    }
};

from collections import deque

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
        
        visited = [False] * n
        components = 0
        
        for i in range(n):
            if not visited[i]:
                components += 1
                queue = deque([i])
                visited[i] = True
                while queue:
                    curr = queue.popleft()
                    for neighbor in adj[curr]:
                        if not visited[neighbor]:
                            visited[neighbor] = True
                            queue.append(neighbor)
        
        return components

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        int components = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int curr = queue.poll();
                    for (int neighbor : adj.get(curr)) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.offer(neighbor);
                        }
                    }
                }
            }
        }
        return components;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Identical to DFS: each node is visited once and each edge is traversed twice. Building the adjacency list is O(E). Total: O(V + E).

Space Complexity: O(V + E)

The adjacency list takes O(V + E). The visited array takes O(V). The queue can hold up to O(V) nodes in the worst case (a star graph where all nodes are neighbors of one central node). Total: O(V + E).

Why This Approach Is Not Efficient

BFS and DFS both achieve O(V + E) time complexity, which is optimal for graph traversal. However, both approaches share a common overhead: they require building a full adjacency list before processing. This takes O(V + E) space.

For scenarios where edges arrive one at a time (streaming) or where you want to dynamically merge components, the graph traversal approach requires rebuilding and reprocessing the entire graph. The Union-Find (Disjoint Set Union) data structure can handle edges incrementally, processing each edge in near-constant time, and can answer component queries at any point without a full traversal.

Additionally, Union-Find with path compression and union by rank achieves an amortized time per operation of O(α(n)), where α is the inverse Ackermann function — effectively constant. This makes it the preferred approach in many practical applications.

Optimal Approach - Union-Find (Disjoint Set Union)

Intuition

Union-Find takes a completely different perspective. Instead of exploring the graph through traversal, we think about it as a grouping problem.

Imagine each node starts as the leader of its own group (a group of one). When we process an edge connecting nodes A and B, we merge their groups into one. At the end, the number of distinct groups remaining is the number of connected components.

The Union-Find data structure supports two operations efficiently:

Find(x): Determine which group node x belongs to (returns the group representative/root).
Union(x, y): Merge the groups containing nodes x and y into a single group.

We start with n groups (one per node). For each edge [a, b], we call Union(a, b). If a and b were already in the same group, nothing changes and the component count stays the same. If they were in different groups, they merge and the component count decreases by 1.

Two key optimizations make this extremely fast:

Path compression: When finding the root, make every node along the path point directly to the root.
Union by rank: Always attach the shorter tree under the taller tree, keeping the structure shallow.

Step-by-Step Explanation

Let's trace with n = 5, edges = [[0, 1], [1, 2], [3, 4]]:

Step 1: Initialize parent = [0, 1, 2, 3, 4] (each node is its own parent). rank = [0, 0, 0, 0, 0]. Components = 5.

Step 2: Process edge [0, 1]. Find(0) = 0, Find(1) = 1. Different roots → union them. Set parent[1] = 0 (attach 1 under 0). Components = 4.

Step 3: Process edge [1, 2]. Find(1): parent[1] = 0, so root is 0. Find(2) = 2. Different roots → union. Set parent[2] = 0. Components = 3.

Step 4: Process edge [3, 4]. Find(3) = 3, Find(4) = 4. Different roots → union. Set parent[4] = 3. Components = 2.

Step 5: All edges processed. Components = 2.

Result: 2 connected components. We started with 5 and reduced by 1 for each edge that connected previously separate components.

Union-Find — Merging Components Edge by Edge — Watch the parent array evolve as each edge merges two components. The component count decreases by 1 each time an edge connects previously separate nodes.

Algorithm

Initialize parent[i] = i for all nodes (each node is its own root).
Initialize rank[i] = 0 for all nodes.
Set components = n.
For each edge [a, b]:
- Call rootA = find(a) and rootB = find(b) with path compression.
- If rootA ≠ rootB:
  - Union by rank: attach the smaller-rank tree under the larger-rank tree.
  - Decrement components.
Return components.

Code

class Solution {
public:
    vector<int> parent, rank_;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;
        
        if (rank_[rootX] < rank_[rootY]) {
            parent[rootX] = rootY;
        } else if (rank_[rootX] > rank_[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank_[rootX]++;
        }
        return true;
    }
    
    int countComponents(int n, vector<vector<int>>& edges) {
        parent.resize(n);
        rank_.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int components = n;
        for (auto& edge : edges) {
            if (unite(edge[0], edge[1])) {
                components--;
            }
        }
        return components;
    }
};

class Solution:
    def countComponents(self, n: int, edges: list[list[int]]) -> int:
        parent = list(range(n))
        rank = [0] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x == root_y:
                return False
            if rank[root_x] < rank[root_y]:
                parent[root_x] = root_y
            elif rank[root_x] > rank[root_y]:
                parent[root_y] = root_x
            else:
                parent[root_y] = root_x
                rank[root_x] += 1
            return True
        
        components = n
        for a, b in edges:
            if union(a, b):
                components -= 1
        
        return components

class Solution {
    private int[] parent;
    private int[] rank;
    
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    private boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;
        
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
    
    public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int components = n;
        for (int[] edge : edges) {
            if (union(edge[0], edge[1])) {
                components--;
            }
        }
        return components;
    }
}

Complexity Analysis

Time Complexity: O(V + E × α(V))

Initialization takes O(V). Processing each edge involves two find calls and one union call. With path compression and union by rank, each operation takes amortized O(α(V)) time, where α is the inverse Ackermann function. For all practical purposes, α(V) ≤ 5 for any conceivable input size, so each operation is effectively O(1). Total: O(V + E).

Space Complexity: O(V)

We store the parent and rank arrays, each of size V. Unlike the DFS/BFS approaches, we do NOT need to build an adjacency list — edges are processed directly. This gives Union-Find a space advantage: O(V) vs O(V + E) for traversal approaches.