Number of Connected Components: Union-Find or DFS

• Connected components are groups of mutually reachable nodes in an undirected graph.
• Union-Find starts with n singletons, merges endpoints of each edge, and decrements the count on each successful merge.
• Path compression flattens the tree toward the root during find, keeping operations fast.
• Union by rank attaches the shallower tree under the deeper one, preventing degenerate chains.
• DFS alternative counts how many traversals are needed to visit all nodes.
• Time is O(V + E * alpha(V)) which is effectively linear; space is O(V).

What is the Number of Connected Components problem?

Given n nodes labeled 0 to n-1 and a list of undirected edges, count the number of connected components. A connected component is a group of nodes where every pair is reachable from each other through edges. This is a fundamental graph problem with applications in network analysis, fraud detection, and social grouping.

package com.bank.service;

public class AccountClusterCounter {
    private int[] parent;
    private int[] rank;
    private int count;

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

        for (int[] edge : edges) {
            union(edge[0], edge[1]);
        }
        return count;
    }

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

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        count--;
    }
}

Why does Union-Find work for this problem?

Each node starts as its own component. When an edge connects two nodes in different components, unioning them merges the components and decrements the count. If the nodes are already in the same component, the count stays the same. After processing all edges, the remaining count is the answer.

Nodes: 0, 1, 2, 3, 4    Edges: [0,1], [1,2], [3,4]

Initial: count = 5, each node is its own component
Edge [0,1]: union(0,1) → count = 4
Edge [1,2]: union(1,2) → count = 3
Edge [3,4]: union(3,4) → count = 2

Final: 2 components: {0,1,2} and {3,4}

How do path compression and union by rank work?

Path compression flattens the tree during find by making every node on the path point directly to the root. Union by rank attaches the shallower tree under the deeper one. Together they keep the trees very flat, giving near-constant amortized time per operation.

// Path compression: flatten during find
private int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // point directly to root
    }
    return parent[x];
}

// Union by rank: shorter tree goes under taller tree
private void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    count--;
}

How does the DFS alternative work?

Build an adjacency list and run a DFS from each unvisited node. Each DFS invocation explores an entire connected component. The number of DFS invocations is the number of components.

public int countComponentsDFS(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }

    boolean[] visited = new boolean[n];
    int components = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            components++;
            dfs(i, adj, visited);
        }
    }
    return components;
}

private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
    visited[node] = true;
    for (int nb : adj.get(node)) {
        if (!visited[nb]) dfs(nb, adj, visited);
    }
}

When should you choose Union-Find over DFS?

| Aspect | Union-Find | DFS |
|--------|-----------|-----|
| Static graph | Works | Simpler to implement |
| Dynamic edges (added over time) | Ideal: O(alpha(n)) per add | Must re-run from scratch |
| Repeated connectivity queries | O(alpha(n)) per query | Must re-run or cache |
| Implementation complexity | Moderate | Simple |
| Space | O(V) for parent/rank | O(V + E) for adjacency list |

What are edge cases?

• No edges: every node is its own component, answer is n.
• Fully connected graph: answer is 1.
• Single node with no edges: answer is 1.
• Duplicate edges: union handles them safely because merging the same component is a no-op.

// Edge case: no edges
// n = 5, edges = []
// Every node is its own component → answer = 5

// Edge case: fully connected
// n = 3, edges = [[0,1],[1,2],[0,2]]
// After all unions → answer = 1

What are common mistakes?

The first mistake is forgetting path compression, which makes find operations O(n) in the worst case instead of near-constant. The second mistake is not checking whether two nodes are already in the same component before decrementing the count. The third mistake is using a directed adjacency list for an undirected graph in the DFS approach.

// WRONG: find without path compression
private int find(int x) {
    while (parent[x] != x) x = parent[x];  // no compression
    return x;
}

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

What should a senior engineer know?

At the National Bank of India, accounts linked by shared attributes formed clusters. The fraud team needed the number of distinct clusters. Because links were discovered incrementally and the cluster count was queried repeatedly, Union-Find was the natural fit: each new link merged clusters in near-constant time, so the current cluster count was always available without rescanning the entire graph. The DFS approach would have required rebuilding the adjacency list and re-traversing the entire graph after each new link.