Number of Connected Components in an Undirected Graph

Problem Description

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [a, b] indicates that there is an edge between a and b in the graph.

Return the number of connected components in the graph.

Examples

Constraints

• 1 ≤ n ≤ 2000
• 0 ≤ edges.length ≤ 5000
• edges[i].length == 2
• 0 ≤ a, b < n
• a != b
• There are no duplicate edges.

Merging Disjoint Sets or Traversal Islands

You can find the number of connected components in two ways:

1. Graph Traversal (DFS/BFS): Build an adjacency list, track visited nodes, and iterate over all nodes. Whenever you hit an unvisited node, run a full traversal (DFS or BFS) to visit its connected island, incrementing the component counter.
2. Union-Find (Disjoint Set Union): Initialize n distinct sets, one for each node, with a component count of n. For each edge [a, b], union the sets containing a and b. If they were in different sets, they merge into one, and we decrement the component count.

Union-Find is the most optimal and elegant solution here because it processes edges directly without needing to construct an adjacency list.

Solution 1: Union-Find (Disjoint Set Union)

Initialize parent pointers and ranks. For each edge, perform union operations with path compression.

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

        int components = n;
        for (int[] edge : edges) {
            if (union(edge[0], edge[1], parent, rank)) {
                components--; // decrement count on successful merge
            }
        }
        return components;
    }

    private int find(int val, int[] parent) {
        int curr = val;
        while (curr != parent[curr]) {
            parent[curr] = parent[parent[curr]]; // path compression
            curr = parent[curr];
        }
        return curr;
    }

    private boolean union(int n1, int n2, int[] parent, int[] rank) {
        int p1 = find(n1, parent);
        int p2 = find(n2, parent);

        if (p1 == p2) return false; // already in the same set

        // union by rank
        if (rank[p1] > rank[p2]) {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }
}

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

        def find(val):
            curr = val
            while curr != parent[curr]:
                parent[curr] = parent[parent[curr]]  # path compression
                curr = parent[curr]
            return curr

        def union(n1, n2):
            p1, p2 = find(n1), find(n2)
            if p1 == p2:
                return False  # already in the same set

            # union by rank
            if rank[p1] > rank[p2]:
                parent[p2] = p1
                rank[p1] += rank[p2]
            else:
                parent[p1] = p2
                rank[p2] += rank[p1]
            return True

        components = n
        for n1, n2 in edges:
            if union(n1, n2):
                components -= 1  # decrement count on successful merge

        return components

#include <vector>
#include <numeric>

class Solution {
private:
    int find(int val, std::vector<int>& parent) {
        int curr = val;
        while (curr != parent[curr]) {
            parent[curr] = parent[parent[curr]]; // path compression
            curr = parent[curr];
        }
        return curr;
    }

    bool unionNodes(int n1, int n2, std::vector<int>& parent, std::vector<int>& rank) {
        int p1 = find(n1, parent);
        int p2 = find(n2, parent);

        if (p1 == p2) return false;

        if (rank[p1] > rank[p2]) {
            parent[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            parent[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }

public:
    int countComponents(int n, std::vector<std::vector<int>>& edges) {
        std::vector<int> parent(n);
        std::iota(parent.begin(), parent.end(), 0);
        std::vector<int> rank(n, 1);

        int components = n;
        for (const auto& edge : edges) {
            if (unionNodes(edge[0], edge[1], parent, rank)) {
                components--;
            }
        }
        return components;
    }
};

Complexity Analysis:

• Time Complexity: O(V + E * α(V)) where α is the inverse Ackermann function, which grows so slowly that it is effectively O(1). This makes Union-Find near-linear O(V + E).
• Space Complexity: O(V) to store the parent and rank arrays.

Where it breaks: Nothing breaks for standard undirected graphs. Union-Find does not work on directed graph reachability because it cannot represent asymmetric relationships.

Common Mistakes

• Not path compressing in the find operation. Without path compression, the tree structure can degenerate into a linear chain, increasing find time complexity to O(V).
• Returning the Union-Find parent counts directly without finding roots. The parent array can contain intermediate values. You must run find(i) on each element to get its true representative root node.
• Forgetting to decrement components count on successful unions. Only decrement the counter if union returns true (a merge actually occurred).

Frequently Asked Questions

How does DFS compare to Union-Find for this problem? DFS is also O(V + E) time, but it requires building an adjacency list, which uses more memory and code. Union-Find operates directly on the edge list, making it faster and cleaner to implement.

What is path compression? Path compression updates the parent pointers of all traversed nodes directly to the root node during the find operation. This keeps tree heights flat, ensuring near O(1) operations.

What does this problem test in interviews? It tests your ability to model graphs, implement basic Disjoint Set Union (DSU) mechanics, and utilize rank and path compression optimizations.

← All Problems