Number of Connected Components in an Undirected Graph

Number of Connected Components in an Undirected Graph - Problem

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

A connected component is a maximal set of vertices such that for every pair of vertices u and v, there is a path connecting them.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: There are 2 connected components: {0,1,2} and {3,4}. Node 0 connects to 1, which connects to 2. Separately, node 3 connects to 4.

Example 2 — No Edges

$ Input: n = 5, edges = []

› Output: 5

💡 Note: With no edges, each node forms its own connected component: {0}, {1}, {2}, {3}, {4}.

Example 3 — Fully Connected

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

› Output: 1

💡 Note: All nodes are connected to each other, forming one connected component: {0,1,2}.

Constraints

1 ≤ n ≤ 2000
1 ≤ edges.length ≤ 5000
edges[i].length == 2
0 ≤ ai ≤ bi < n
ai != bi
There are no repeated edges

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with n=5 nodes and edges [[0,1],[1,2],[3,4]]

Find Components

Use graph traversal to group connected nodes

Count Result

Return number of separate components found

Key Takeaway

🎯 Key Insight: Use graph traversal to group nodes - each traversal starting point represents a new connected component

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is that connected components are groups of nodes that can reach each other through edges. We can use graph traversal (DFS or BFS) to identify these groups. Start from each unvisited node, explore its entire connected component, and count how many times we need to start a new traversal. Time: O(V + E), Space: O(V + E)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Iterative Stack	O(V + E)	O(V + E)	Use iterative DFS with explicit stack to avoid recursion overhead and stack overflow
Brute Force DFS	O(V + E)	O(V + E)	Visit each unvisited node and explore its entire connected component using DFS
Breadth-First Search (BFS)	O(V + E)	O(V + E)	Use BFS with queue to explore each connected component level by level

Optimized DFS with Iterative Stack — Algorithm Steps

Build adjacency list from edges
Use explicit stack for DFS instead of recursion
For each unvisited node, push to stack and explore iteratively
Count connected components

Visualization

Tap to expand

2. Add unvisited neighbors
3. Mark as visited
4. Repeat until emptyIterative DFS avoids recursion stack overflow

Step-by-Step Walkthrough

Initialize

Push starting node to stack, mark visited

Process

Pop node, push unvisited neighbors

Complete

Stack empty = one component found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int n, int** edges, int edgesSize) {
    // Build adjacency list
    int** adj = (int**)malloc(n * sizeof(int*));
    int* adjSizes = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        adj[i] = (int*)malloc(n * sizeof(int));
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        adj[u][adjSizes[u]++] = v;
        adj[v][adjSizes[v]++] = u;
    }
    
    bool* visited = (bool*)calloc(n, sizeof(bool));
    int components = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // Iterative DFS with stack
            int* stack = (int*)malloc(n * sizeof(int));
            int stackSize = 0;
            
            stack[stackSize++] = i;
            visited[i] = true;
            
            while (stackSize > 0) {
                int node = stack[--stackSize];
                
                for (int j = 0; j < adjSizes[node]; j++) {
                    int neighbor = adj[node][j];
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        stack[stackSize++] = neighbor;
                    }
                }
            }
            
            free(stack);
            components++;
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(adj[i]);
    }
    free(adj);
    free(adjSizes);
    free(visited);
    
    return components;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    int edges[1000][2];
    int edgesSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                edges[edgesSize][0] = atoi(ptr);
                while (*ptr != ',') ptr++;
                ptr++;
                edges[edgesSize][1] = atoi(ptr);
                edgesSize++;
                while (*ptr != ']') ptr++;
                ptr++;
            } else {
                ptr++;
            }
        }
    }
    
    int* edgePtrs[1000];
    for (int i = 0; i < edgesSize; i++) {
        edgePtrs[i] = edges[i];
    }
    
    printf("%d\n", solution(n, edgePtrs, edgesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Visit each vertex once and traverse each edge once during iterative DFS

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list O(V + E), visited array O(V), explicit stack O(V) worst case

✓ Linear Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with Iterative Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler