323. Number of Connected Components in an Undirected Graph (Medium)

Problem

Given n nodes labeled 0 to n - 1 and a list of undirected edges, return the number of connected components.

Example

• n = 5, edges = [[0,1],[1,2],[3,4]] → 2
• n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] → 1

LeetCode 323 (premium) · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: DFS

Walk each unvisited node; each DFS covers one component.

Python

from collections import defaultdict

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:                  # L1: E iterations
        graph[u].append(v)              # L2: O(1) each
        graph[v].append(u)              # L3: O(1) each

    visited = set()

    def dfs(node):
        stack = [node]                  # L4: O(1) init
        while stack:                    # L5: visits each node once
            x = stack.pop()            # L6: O(1)
            if x in visited:
                continue
            visited.add(x)             # L7: O(1)
            for nb in graph[x]:        # L8: each edge traversed twice total
                if nb not in visited:
                    stack.append(nb)   # L9: O(1)

    count = 0
    for i in range(n):                 # L10: V iterations
        if i not in visited:
            count += 1
            dfs(i)                     # L11: O(V + E) total across all calls
    return count

TypeScript

function countComponents(n: number, edges: number[][]): number {
    const graph: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {       // L1: E iterations
        graph[u].push(v);               // L2: O(1) each
        graph[v].push(u);               // L3: O(1) each
    }

    const visited = new Set<number>();

    function dfs(node: number): void {
        const stack = [node];           // L4: O(1) init
        while (stack.length > 0) {      // L5: visits each node once
            const x = stack.pop()!;     // L6: O(1)
            if (visited.has(x)) continue;
            visited.add(x);             // L7: O(1)
            for (const nb of graph[x]) {  // L8: each edge traversed twice total
                if (!visited.has(nb)) stack.push(nb);  // L9: O(1)
            }
        }
    }

    let count = 0;
    for (let i = 0; i < n; i++) {       // L10: V iterations
        if (!visited.has(i)) {
            count++;
            dfs(i);                     // L11: O(V + E) total across all calls
        }
    }
    return count;
}

Go

func countComponents(n int, edges [][]int) int {
    graph := make([][]int, n)
    for _, e := range edges {                    // L1: E iterations
        graph[e[0]] = append(graph[e[0]], e[1]) // L2
        graph[e[1]] = append(graph[e[1]], e[0]) // L3
    }
    visited := make([]bool, n)
    dfs := func(node int) {
        stack := []int{node}                     // L4
        for len(stack) > 0 {                     // L5
            x := stack[len(stack)-1]; stack = stack[:len(stack)-1] // L6
            if visited[x] { continue }
            visited[x] = true                    // L7
            for _, nb := range graph[x] {        // L8
                if !visited[nb] { stack = append(stack, nb) } // L9
            }
        }
    }
    count := 0
    for i := 0; i < n; i++ {                    // L10
        if !visited[i] { count++; dfs(i) }      // L11
    }
    return count
}

Swift

final class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var graph = Array(repeating: [Int](), count: n)
        for edge in edges { graph[edge[0]].append(edge[1]); graph[edge[1]].append(edge[0]) }
        var seen = Set<Int>(), components = 0
        func visit(_ node: Int) {
            if !seen.insert(node).inserted { return }
            for next in graph[node] { visit(next) }
        }
        for node in 0..<n where !seen.contains(node) { components += 1; visit(node) }
        return components
    }
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(edges).

Line	Per-call cost	Times executed	Contribution
L1-L3 (build adjacency list)	$O(1)$ per edge	E	$O(E)$
L10 (outer loop)	$O(1)$	V	$O(V)$
L5-L9 (DFS stack loop)	$O(1)$ per node/edge	V nodes + 2E edge-visits total	$O(V + E)$ ← dominates

Each node is added to visited exactly once and each edge is pushed onto the stack at most twice (once per direction). The total work across all dfs() calls is $O(V + E)$, not $O(V + E)$ per component.

Complexity

• Time: $O(V + E)$, driven by L5-L9 summed across all DFS calls.
• Space: $O(V + E)$ for the adjacency list and visited set; the stack holds at most V entries.

Approach 2: Union-Find (optimal)

Start with n components. Each successful union reduces the count by 1.

Python

def count_components(n, edges):
    parent = list(range(n))             # L1: O(V)
    count = n                           # L2: O(1)

    def find(x):
        while parent[x] != x:          # L3: follows path to root
            parent[x] = parent[parent[x]]  # L4: path halving
            x = parent[x]
        return x

    for u, v in edges:                  # L5: E iterations
        ru, rv = find(u), find(v)      # L6: near-O(1) amortized per find
        if ru != rv:
            parent[ru] = rv            # L7: O(1) union
            count -= 1                 # L8: O(1)
    return count

TypeScript

function countComponents(n: number, edges: number[][]): number {
    const parent = Array.from({ length: n }, (_, i) => i);  // L1: O(V)
    let count = n;                                           // L2: O(1)

    function find(x: number): number {
        while (parent[x] !== x) {                           // L3: follows path to root
            parent[x] = parent[parent[x]];                  // L4: path halving
            x = parent[x];
        }
        return x;
    }

    for (const [u, v] of edges) {                           // L5: E iterations
        const ru = find(u), rv = find(v);                   // L6: near-O(1) amortized
        if (ru !== rv) {
            parent[ru] = rv;                                // L7: O(1) union
            count--;                                        // L8: O(1)
        }
    }
    return count;
}

Go

func countComponents(n int, edges [][]int) int {
    parent := make([]int, n)
    for i := range parent { parent[i] = i }     // L1: O(V)
    count := n                                   // L2

    var find func(x int) int
    find = func(x int) int {
        for parent[x] != x {                     // L3
            parent[x] = parent[parent[x]]        // L4: path halving
            x = parent[x]
        }
        return x
    }

    for _, e := range edges {                    // L5: E iterations
        ru, rv := find(e[0]), find(e[1])         // L6
        if ru != rv {
            parent[ru] = rv                      // L7: union
            count--                              // L8
        }
    }
    return count
}

Swift

struct UnionFind {
    var parent: [Int]
    var rank: [Int]
    init(_ count: Int) { parent = Array(0..<count); rank = Array(repeating: 0, count: count) }
    mutating func find(_ value: Int) -> Int {
        if parent[value] != value { parent[value] = find(parent[value]) }
        return parent[value]
    }
    mutating func union(_ left: Int, _ right: Int) -> Bool {
        var a = find(left), b = find(right)
        if a == b { return false }
        if rank[a] < rank[b] { swap(&a, &b) }
        parent[b] = a
        if rank[a] == rank[b] { rank[a] += 1 }
        return true
    }
}

final class Solution {
    func countComponents(_ n: Int, _ edges: [[Int]]) -> Int {
        var unionFind = UnionFind(n), components = n
        for edge in edges where unionFind.union(edge[0], edge[1]) { components -= 1 }
        return components
    }
}

Where the time goes, line by line

Variables: V = n (number of nodes), E = len(edges).

Line	Per-call cost	Times executed	Contribution
L1 (init parent array)	$O(V)$	1	$O(V)$
L5-L8 (edge processing loop)	$O(alpha(V)$) per edge	E	$O(E * alpha(V)$) ← dominates

Complexity

• Time: $O(V + E * alpha(V)$), driven by L5-L8. Effectively $O(V + E)$ in practice.
• Space: $O(V)$ for the parent array; no adjacency list needed.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
DFS	$O(V + E)$	$O(V + E)$
BFS	$O(V + E)$	$O(V + E)$
Union-Find	$O(V + E · alpha(V)$)	$O(V)$

All optimal. Pick union-find when edges arrive online or you also need “are u and v in the same component?” queries.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_323.py and run.
# Uses the canonical implementation (Approach 2: Union-Find).

def count_components(n, edges):
    parent = list(range(n))
    count = n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            count -= 1
    return count

def _run_tests():
    # Canonical example: two components
    assert count_components(5, [[0, 1], [1, 2], [3, 4]]) == 2

    # Single component spanning all nodes
    assert count_components(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) == 1

    # No edges: every node is its own component
    assert count_components(4, []) == 4

    # Single node, no edges
    assert count_components(1, []) == 1

    # All nodes fully connected (complete graph on 3)
    assert count_components(3, [[0, 1], [1, 2], [0, 2]]) == 1

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function countComponents(n: number, edges: number[][]): number {
    const parent = Array.from({ length: n }, (_, i) => i);
    let count = n;
    function find(x: number): number {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
    for (const [u, v] of edges) {
        const ru = find(u), rv = find(v);
        if (ru !== rv) { parent[ru] = rv; count--; }
    }
    return count;
}

console.assert(countComponents(5, [[0,1],[1,2],[3,4]]) === 2);
console.assert(countComponents(5, [[0,1],[1,2],[2,3],[3,4]]) === 1);
console.assert(countComponents(4, []) === 4);
console.assert(countComponents(1, []) === 1);
console.assert(countComponents(3, [[0,1],[1,2],[0,2]]) === 1);
console.log("all tests pass");

Related data structures

• Graphs, connected components via any of the three

Related concepts

• Union Find, the component tracking structure for connectivity as edges are processed.
• Graph Traversal, the visited set model for exploring nodes and edges without repetition.