☕ DSA Java Articles

Topics › Graphs › Learning

Connected Components

Medium TUF ID 528 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given n vertices labelled 0..n-1 and a list of undirected edges {u, v}. A connected component is a maximal group of vertices in which every vertex can reach every other one along edges. Return the number of connected components.

This is the idea the A2Z lecture on connected components is built around: a graph does not have to be in one piece, so any algorithm that explores it from a single start vertex may miss parts of it. The Blind 75 version (LeetCode 323) asks for exactly this count.

Constraints: 1 ≤ n ≤ 2000, at most 5000 edges. LeetCode promises no repeated edges, but the solutions below also handle repeated edges and self-loops, since other judges are less strict.

Example 1

n = 5, edges = [[0,1], [1,2], [3,4]]
answer = 2          // {0, 1, 2} and {3, 4}

Example 2

n = 6, edges = [[0,1], [1,2], [2,0], [3,4]]
answer = 3          // the triangle {0, 1, 2}, the pair {3, 4}, and vertex 5 on its own

Vertex 5 in example 2 has no edges at all, but it is still a component. Isolated vertices are the easiest thing to forget.

Approach 1: Brute force, label propagation

Intuition. Give every vertex a label, initially its own number. An edge says its two ends belong together, so whenever an edge joins two different labels, overwrite both with the smaller one. Labels can only flow along edges, so they never cross between components; and as long as two neighbours disagree something still changes. When a full sweep over the edges changes nothing, every component has collapsed to a single label: the smallest vertex number in it. Counting components is then counting the vertices whose label is still their own number.

Algorithm.

  1. Set label[i] = i for every vertex.
  2. Repeat: for every edge {u, v}, set both labels to min(label[u], label[v]); remember whether anything changed.
  3. Stop after a sweep with no change.
  4. Return how many i satisfy label[i] == i.
static int bruteForce(int n, int[][] edges) {
    int[] label = new int[n];
    for (int i = 0; i < n; i++) label[i] = i;
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int[] e : edges) {
            int low = Math.min(label[e[0]], label[e[1]]);
            if (label[e[0]] != low || label[e[1]] != low) {
                label[e[0]] = low;
                label[e[1]] = low;
                changed = true;
            }
        }
    }
    int components = 0;
    for (int i = 0; i < n; i++) {
        if (label[i] == i) components++;              // each component ends up labelled by its smallest vertex
    }
    return components;
}

Complexity. Time O(V * E): each sweep costs O(E), and the smallest label of a component can need up to V - 1 sweeps to walk to its far end, since it may advance only one edge per sweep. Space O(V) for the labels.

The worst case is easy to trigger: a path 0-1-2-...-1999 whose edges are listed from the far end, {1998, 1999}, {1997, 1998}, .... Label 0 then moves one step per sweep. The test file includes exactly this input. For V = 2000 that is a few million operations, fine here, but the bound is quadratic and we can do linear.

Approach 2: Optimal, traversal from every unvisited vertex

Intuition. A BFS (or DFS) started at a vertex visits precisely the vertices of that vertex’s component, no more and no less. So loop over all vertices in order; whenever you meet one that has not been visited yet, it must belong to a component nobody has explored, so count one and run a traversal from it to mark the whole component. Vertices already marked are skipped. Each component is therefore counted exactly once, at its first vertex in label order.

This outer loop is the important lesson of the lecture. Every graph algorithm that has to touch all vertices, cycle detection, bipartite checks, topological sort, uses the same pattern: for each vertex, if not visited, traverse from it.

Algorithm.

  1. Build an adjacency list, adding each edge in both directions.
  2. For start = 0 .. n-1: if start is visited, skip it. Otherwise increment the count, mark start, and BFS from it, marking every newly reached vertex.
  3. Return the count.
static int optimalTraversal(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    int components = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    for (int start = 0; start < n; start++) {
        if (visited[start]) continue;                 // already swallowed by an earlier component
        components++;
        visited[start] = true;
        queue.add(start);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }
    }
    return components;
}

Dry run on example 2 (n = 6, triangle 0-1-2, pair 3-4, isolated 5):

start visited before? action visited after
0 no count = 1, BFS reaches 0, 1, 2 {0, 1, 2}
1 yes skip  
2 yes skip  
3 no count = 2, BFS reaches 3, 4 {0..4}
4 yes skip  
5 no count = 3, BFS reaches only 5 {0..5}

Complexity. Time O(V + E): building the list is O(V + E), every vertex enters the queue once over the whole run, and every adjacency list is scanned once. Space O(V + E) for the list, plus O(V) for the visited array and queue.

BFS is used here because it needs no recursion. A recursive DFS works just as well and is equally common; on very long paths it can overflow the call stack, which BFS never does.

Approach 3: Optimal, union-find

Intuition. Start with n separate singletons, one per vertex, so n components. Each edge either joins two different groups, merging them and reducing the count by one, or connects two vertices that are already in the same group and changes nothing. A disjoint set union (union-find) structure answers “which group is x in?” almost in constant time, so we can process the edges in any order, without building an adjacency list.

find walks up parent pointers to the root that represents the group, and path halving (pointing each visited node at its grandparent) keeps the trees shallow. Union by size hangs the smaller tree under the larger one so the trees never get deep.

Algorithm.

  1. parent[i] = i, size[i] = 1, components = n.
  2. For each edge {u, v}: find the roots a and b. If they are equal, continue. Otherwise attach the smaller tree to the larger and decrement components.
  3. Return components.
static int optimalUnionFind(int n, int[][] edges) {
    int[] parent = new int[n], size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    int components = n;
    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) continue;                         // already in the same component: nothing merges
        if (size[a] < size[b]) {
            int t = a;
            a = b;
            b = t;
        }
        parent[b] = a;                                // hang the smaller tree under the larger
        size[a] += size[b];
        components--;
    }
    return components;
}

static int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];                // path halving keeps the trees shallow
        x = parent[x];
    }
    return x;
}

Complexity. Time O(V + E * α(V)), where α is the inverse Ackermann function, at most 4 for any input you will ever see. Space O(V) for the two arrays.

Union-find shines when edges arrive one by one and you need the component count after each one, or when the graph is too large to store as an adjacency list. For a single static count, the traversal is just as good.

Edge cases and pitfalls