219. Number of Connected Components in an Undirected Graph

Start with n separate components. Every edge that unites two different sets merges two components into one, decrementing the count.

Union-Find

Begin with each node in its own set — count = n. For each edge (a, b), find the roots of a and b. If they differ, the edge connects two previously-separate components: union them and do count -= 1. Edges inside an already-connected component change nothing.

find uses path compression (point nodes closer to the root) so operations are nearly O(1) amortised.

Walk-through

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

• start count 5.
• (0,1): roots 0,1 differ → union → count 4.
• (1,2): roots 0,2 differ → union → count 3.
• (3,4): roots 3,4 differ → union → count 2.
• Answer 2 (components {0,1,2} and {3,4}).

Complexity

• Time: O((n + e)·α(n)) ≈ near-linear.
• Space: O(n) for the parent array.

class Solution {
    private int[] parent;

    public int countComponents(int n, int[][] edges) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int count = n;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) {
                parent[ra] = rb;
                count--;
            }
        }
        return count;
    }

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