Number of Connected Components in an Undirected Graph

Think of people in a room. Some hold hands in small clusters. Others stand alone. How many separate clusters are there? That is what this problem asks about a graph. Counting these clusters is a core graph skill, and it gives you a second reason to learn union-find.

🎯 The Problem

You get a graph. You must count how many separate groups it has.

The rules:

• The nodes are labeled 0 to n - 1.
• Each edge [a, b] connects node a and node b.
• The connection works both ways, so this is an undirected graph.
• A group where you can travel between every node is one connected component.
• Return the number of connected components.

For example, with 5 nodes and edges [[0,1],[1,2],[3,4]], nodes 0, 1, and 2 form one group and 3 and 4 form another. So the answer is 2.

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

Explanation: {0, 1, 2} is one component and {3, 4} is another.

Here is the graph. You can see the two separate clusters clearly.

🐢 Approach 1: DFS Over an Adjacency List (Better)

The idea in one line: walk each cluster once and count one for every fresh cluster you start.

The idea:

• Build an adjacency list, which is the list of neighbors for each node.
• DFS (depth first search) follows one path as deep as it goes, then backs up.

How it works:

• Loop over every node.
• When you reach a node not visited yet, you found a new cluster. Add one to the count.
• Run a DFS from that node and mark every node it can reach as visited.
• Marking the whole cluster means you count each cluster only once.

Why it works but costs more:

• It needs the adjacency list and a recursion stack.
• Time is O(V + E). Space is O(V + E) for the list and the stack.

Here is the adjacency-list DFS code:

def count_components(n, edges):
    graph = [[] for _ in range(n)]
    for a, b in edges:
        graph[a].append(b); graph[b].append(a)
    seen = set()
    def dfs(node):
        seen.add(node)
        for nei in graph[node]:
            if nei not in seen: dfs(nei)
    count = 0
    for i in range(n):
        if i not in seen:
            count += 1; dfs(i)
    return count

⚡ Approach 2: Union-Find (Best)

The idea in one line: start with every node alone, then merge groups as edges arrive and count the merges.

The idea:

• Union-find tracks which group each node is in and merges two groups fast.
• It is also called a disjoint set, because the groups never overlap.
• No graph traversal and no adjacency list needed.

How it works:

• Treat every node as its own group. So with n nodes you start with n groups.
• Keep a parent array. Following parents up leads to the top node, the root.
• Two nodes share a group when they share a root.
• find(x) walks up to the root. union(a, b) points one root at the other.
• Read each edge and union its two nodes.
• Start the count at n. Each union that merged two separate groups lowers it by one.
• Edges between already-joined nodes change nothing.

Why it is fast:

• Path compression points each node on the find path straight at the root.
• Union by rank attaches the shorter group under the taller one.
• Together they make each operation almost constant time.

Here is the count dropping as we union each edge in the example.

Steps to Solve

1. Create a parent array where every node is its own parent, and a rank array of zeros.
2. Start a counter at n, since every node begins as its own group.
3. Write find(x) that walks up to the root and points each node along the way straight to the root.
4. Write union(a, b) that finds both roots and attaches the lower-rank root under the higher-rank one.
5. For each edge, union the two nodes. If the union actually merged two groups, lower the counter by one.
6. Return the counter.

#include <stdio.h>

#define MAXN 1000

int parent[MAXN];
int rnk[MAXN];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}

int unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return 0;            // already in same group
    if (rnk[ra] < rnk[rb]) parent[ra] = rb;          // union by rank
    else if (rnk[ra] > rnk[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rnk[ra]++; }
    return 1;                          // a real merge happened
}

int countComponents(int n, int edges[][2], int m) {
    for (int i = 0; i < n; i++) { parent[i] = i; rnk[i] = 0; }
    int count = n;
    for (int i = 0; i < m; i++) {
        if (unite(edges[i][0], edges[i][1])) count--; // one fewer group
    }
    return count;
}

int main(void) {
    int edges[][2] = {{0, 1}, {1, 2}, {3, 4}};
    int result = countComponents(5, edges, 3);
    printf("%d\n", result);
    return 0;
}

2

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent, rnk;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}

bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;        // already in same group
    if (rnk[ra] < rnk[rb]) parent[ra] = rb;          // union by rank
    else if (rnk[ra] > rnk[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rnk[ra]++; }
    return true;                       // a real merge happened
}

int countComponents(int n, vector<vector<int>>& edges) {
    parent.assign(n, 0);
    rnk.assign(n, 0);
    for (int i = 0; i < n; i++) parent[i] = i;

    int count = n;
    for (auto& e : edges) {
        if (unite(e[0], e[1])) count--;  // one fewer group
    }
    return count;
}

int main() {
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {3, 4}};
    cout << countComponents(5, edges) << endl;
    return 0;
}

2

public class ConnectedComponents {
    static int[] parent;
    static int[] rank;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path compression by halving
            x = parent[x];
        }
        return x;
    }

    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;        // already in same group
        if (rank[ra] < rank[rb]) parent[ra] = rb;        // union by rank
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;                       // a real merge happened
    }

    public static 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 count = n;
        for (int[] e : edges) {
            if (union(e[0], e[1])) count--;  // one fewer group
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {1, 2}, {3, 4}};
        System.out.println(countComponents(5, edges));
    }
}

2

def count_components(n, edges):
    parent = list(range(n))   # each node is its own parent
    rank = [0] * n            # rough height of each group

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return False                 # already in same group
        if rank[ra] < rank[rb]:          # union by rank
            parent[ra] = rb
        elif rank[ra] > rank[rb]:
            parent[rb] = ra
        else:
            parent[rb] = ra
            rank[ra] += 1
        return True                      # a real merge happened

    count = n
    for a, b in edges:
        if union(a, b):
            count -= 1                    # one fewer group
    return count


n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(count_components(n, edges))

2

function countComponents(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i); // self parent
  const rank = new Array(n).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]); // path compression
    return parent[x];
  }

  function union(a, b) {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return false;        // already in same group
    if (rank[ra] < rank[rb]) parent[ra] = rb;        // union by rank
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;                        // a real merge happened
  }

  let count = n;
  for (const [a, b] of edges) {
    if (union(a, b)) count--;           // one fewer group
  }
  return count;
}

const n = 5;
const edges = [[0, 1], [1, 2], [3, 4]];
console.log(countComponents(n, edges));

2

Let us walk through the Python version line by line, because the counting idea is the whole trick.

parent = list(range(n)) makes every node its own parent. So at the start each node is alone. rank = [0] * n gives every group rank zero, since a single node has no height yet.

Inside find(x), the check if parent[x] != x: asks whether x is the root. The root is the only node that points to itself. If not, parent[x] = find(parent[x]) finds the true root and also points x straight at it. That is path compression, and it keeps later lookups short.

Inside union(a, b), we get both roots first. if ra == rb: return False means the two nodes were already in the same group, so no merge happens. The rank lines attach the shorter group under the taller one and bump the rank only when the two heights tie.

count = n starts the answer assuming every node is separate. Then if union(a, b): count -= 1 is the key line. A successful union joined two different groups into one, so the number of groups drops by one. Edges between already-joined nodes return False, so they do not change the count. When the loop ends, count holds the number of connected components.

⏱️ Time and Space Complexity

The DFS approach builds an adjacency list and visits every node and edge once, so it is O(V + E) time and O(V + E) space. Union-find skips the adjacency list. With path compression and union by rank, each operation is almost constant time, the inverse Ackermann alpha of n, which stays tiny. So union-find runs in about O(E * alpha(V)) time and O(V) space. Both are fast. Union-find wins on memory because it stores only two small arrays.

🧩 Key Takeaways

• ✅ A connected component is a group where you can travel between every node.
• ✅ Union-find starts with every node alone, so the count begins at n.
• ✅ Every union that merges two different groups lowers the count by one.
• ✅ Path compression and union by rank keep each operation almost constant time.
• ✅ DFS also solves it in O(V + E), but union-find uses less memory.

🚀 What’s Next?

• Graph Valid Tree
• Redundant Connection