Number of Connected Components in an Undirected Graph

Medium · Graphs · Explanation and code example

Disjoint Set Union (Rank | Size)

How it works

Disjoint Set Union (DSU) groups nodes into connected components efficiently.

  • Start by assuming each node is its own component
  • When we process an edge (u, v):
    • If u and v are already in the same set, nothing changes
    • If they are in different sets, we merge them and the number of components decreases by 1
  • Using union by rank/size + path compression keeps operations fast

At the end, the number of remaining sets is the number of connected components.

Steps

  1. Initialize DSU with n nodes, each node as its own parent.
  2. Set components = n.
  3. For each edge (u, v):
    • If union(u, v) is successful (they were separate):
      • Decrement components by 1
  4. Return components.

Complexity

  • Time complexity: O(V + (E * α(V)))
  • Space complexity: O(V)

Where V is the number of vertices and E is the number of edges in the graph. α() is used for amortized complexity.

Things to watch for

Forgetting Isolated Nodes

When there are no edges, each node is its own component. Solutions that only iterate through edges will miss nodes with no connections and return 0 instead of n.

Building a Directed Graph Instead of Undirected

Edges must be added in both directions. Adding only adj[u].append(v) without adj[v].append(u) causes incomplete traversals and overcounts components.

Not Marking Nodes as Visited Before Exploring

In BFS/DFS, marking a node as visited only after processing (instead of when first discovered) can cause nodes to be added to the queue multiple times, leading to incorrect counts or infinite loops.

Python code example

from typing import List

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, node):
        cur = node
        while cur != self.parent[cur]:
            self.parent[cur] = self.parent[self.parent[cur]]
            cur = self.parent[cur]
        return cur

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.rank[pv] > self.rank[pu]:
            pu, pv = pv, pu
        self.parent[pv] = pu
        self.rank[pu] += self.rank[pv]
        return True

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        dsu = DSU(n)
        res = n
        for u, v in edges:
            if dsu.union(u, v):
                res -= 1
        return res

C++ code example

class DSU {
public:
    vector<int> parent;
    vector<int> rank;

    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int node) {
        int cur = node;
        while (cur != parent[cur]) {
            parent[cur] = parent[parent[cur]];
            cur = parent[cur];
        }
        return cur;
    }

    bool unionSets(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) {
            return false;
        }
        if (rank[pv] > rank[pu]) {
            swap(pu, pv);
        }
        parent[pv] = pu;
        rank[pu] += rank[pv];
        return true;
    }
};

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        DSU dsu(n);
        int res = n;
        for (auto& edge : edges) {
            if (dsu.unionSets(edge[0], edge[1])) {
                res--;
            }
        }
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations