Number of Connected Components In An Undirected Graph

MEDIUM✓ CHIP-TIMEDLC #323 — FULL STATEMENT ↗

The drill: Given n nodes labeled 0 to n−1 and a list of undirected edges between them, count how many separate clusters the nodes split into — where a cluster is any group reachable from each other through the given edges.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A set of n nodes labeled 0 through n−1 arrives with a list of undirected edges connecting some of them. The task is to count how many separate clusters the nodes end up split into, where a cluster is any group reachable from each other through those edges.

A node with no edges at all still counts as its own cluster of one — nothing in the input guarantees every node touches an edge, so isolated nodes are entirely possible and expected.

The answer is a single number: the count of distinct clusters once every edge has been accounted for, whether that's one big connected graph or many small disconnected pieces.

EX 01

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

→ 2

A CHAIN OF THREE AND A PAIR

EX 02

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

→ 1

ONE CHAIN SPANS ALL FIVE

EX 03

n = 1 · edges = []

→ 1

A SINGLE NODE IS ITS OWN CLUSTER

up to a few thousand nodes and edges
edges are undirected, and a pair may only appear once
a node with no edges still forms its own one-node cluster
answer is a single integer cluster count

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Nodes with no path between them belong to different clusters, no matter how the edge list happens to be ordered. What operation merges two nodes into the same cluster the instant an edge connects them?

HINT 2 THE STRUCTURE

Start by assuming every node is its own cluster — n of them. Each edge either joins two clusters that were still separate, or reconnects two nodes already in the same one and changes nothing.

HINT 3 ONE STEP FROM THE ANSWER

Union-Find each edge's endpoints, and only decrement a running cluster count when the union actually merges two different roots. Whatever count is left when every edge is processed is the answer.

COACH'S BOARD — THE PATTERN, STEP BY STEP

COUNTING THE CLUSTERSPATTERN · UNION-FINDn = 5 · edges: (0,1) (1,2) (3,4)

STEP 1

5 nodes start as 5 separate clusters. Every union that actually merges two different clusters shrinks that count by one.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/number-of-connected-components-in-an-undirected-graph.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

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

        components = n
        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                components -= 1
        return components

TIME O(V+E·Α(V))SPACE O(V)PYTHON · RACE PACE · 17 LN

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = [False] * n
        components = 0
        for start in range(n):
            if visited[start]:
                continue
            components += 1
            queue = collections.deque([start])
            visited[start] = True
            while queue:
                node = queue.popleft()
                for nxt in graph[node]:
                    if not visited[nxt]:
                        visited[nxt] = True
                        queue.append(nxt)
        return components

TIME O(V+E)SPACE O(V+E)PYTHON · TRAINING PACE · 22 LN

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int components = n;
        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra != rb) {
                parent[ra] = rb;
                components--;
            }
        }
        return components;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

TIME O(V+E·Α(V))SPACE O(V)JAVA · RACE PACE · 25 LN

class Solution {
    public int countComponents(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[n];
        int components = 0;
        for (int start = 0; start < n; start++) {
            if (visited[start]) continue;
            components++;
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(start);
            visited[start] = true;
            while (!queue.isEmpty()) {
                int node = queue.poll();
                for (int nxt : graph.get(node)) {
                    if (!visited[nxt]) {
                        visited[nxt] = true;
                        queue.add(nxt);
                    }
                }
            }
        }
        return components;
    }
}

TIME O(V+E)SPACE O(V+E)JAVA · TRAINING PACE · 30 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED