Back to Linked List
Q3Question 3 of 24

Number of Connected Components: union nodes, count roots

Key Concepts
  • Start with n components (each node is its own set) and decrement by one for each successful union
  • A union that merges two already-connected nodes returns false and does not change the count
  • Union-Find with path compression and union by rank gives near-constant time per operation
  • The final counter value equals the number of distinct roots, which is the component count
  • This approach handles edges streaming in incrementally (online), unlike DFS which needs the full graph upfront
  • Time is O(E * alpha(N)) which is effectively O(E), space is O(N) for parent and rank arrays

Definition

Start with n components and subtract one for every edge that merges two different sets; what remains is the count.
  • Union-Find – a data structure that tracks disjoint sets, supporting find (which set does this node belong to?) and union (merge two sets).
  • Component counting – start with n singleton sets; each successful union reduces the component count by one.
  • Redundant edge – an edge between two nodes already in the same set does not change the count.
  • Optimizations – path compression flattens the tree on find; union by rank keeps it shallow; together they give near-constant amortized time.
  • Complexity – O(E * alpha(N)) time, O(N) space.

The National Bank of India has n branches with no connections. Each new settlement cable connects two branches. Whenever a cable joins two branches not yet in the same network, the number of separate networks drops by one. Redundant cables within an already-connected network change nothing. At the end, the count of independent networks is the answer.

Understanding the Concepts

What is the connected components problem?

Given n nodes labeled 0 to n-1 and a list of undirected edges, count how many connected components exist. A connected component is a maximal group of nodes where every node can reach every other node through some path.

JAVA
package com.bank.model;

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i; // each node is its own root
        }
    }

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

    public boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false; // already connected
        if (rank[rx] < rank[ry]) { parent[rx] = ry; }
        else if (rank[rx] > rank[ry]) { parent[ry] = rx; }
        else { parent[ry] = rx; rank[rx]++; }
        return true; // merged two different sets
    }
}

How do you count components with Union-Find?

Initialize a counter to n (each node is its own component). For each edge, call union. If union returns true (merged two different sets), decrement the counter. The final counter value is the component count.

JAVA
package com.bank.service;

import com.bank.model.UnionFind;

public class ComponentCounter {
    public static int countComponents(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        int components = n;

        for (int[] edge : edges) {
            if (uf.union(edge[0], edge[1])) {
                components--;
            }
        }
        return components;
    }

    public static void main(String[] args) {
        // 5 branches, some connected
        int n = 5;
        int[][] edges = {{0, 1}, {1, 2}, {3, 4}};
        // Components: {0,1,2} and {3,4} = 2

        System.out.println("Connected components: " + countComponents(n, edges));
    }
}
TEXT
Connected components: 2

Why does a redundant edge not change the count?

When you try to union two nodes that already share a root, the find calls return the same root, and the union method returns false without modifying anything. The counter stays the same because no new connectivity was added.

JAVA
// Edge between already-connected nodes
int[][] edges = {{0, 1}, {1, 2}, {0, 2}}; // 0-2 is redundant
// union(0,1) → true, components = 2
// union(1,2) → true, components = 1
// union(0,2) → false (already same set), components stays 1

How does path compression work?

Path compression flattens the tree during find by making every node on the path point directly to the root. This keeps future finds nearly constant time.

JAVA
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // point directly to root
    }
    return parent[x];
}

// Before compression: 0 → 1 → 2 → 3 (root)
// After find(0):      0 → 3, 1 → 3, 2 → 3 (all point to root)

How is this different from DFS flood-fill?

DFS builds an adjacency list, then visits each unvisited node and floods its component. Both count components correctly, but Union-Find handles edges streaming in incrementally (online), while DFS needs the full graph upfront.

| Feature | Union-Find | DFS Flood-Fill |
|---|---|---|
| Online (streaming edges) | Yes | No (needs full graph) |
| Time | O(E * alpha(N)) | O(N + E) |
| Space | O(N) | O(N + E) for adjacency list |
| Incremental count | Yes (counter updates per edge) | No (must re-traverse) |

JAVA
// DFS approach: needs adjacency list built first
public static 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[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            count++;
            dfs(i, adj, visited);
        }
    }
    return count;
}

What are the edge cases?

No edges (each node is its own component), all nodes connected (one component), and self-loops.

JAVA
package com.bank.service;

public class ComponentEdgeCases {
    public static void main(String[] args) {
        // No edges: each node alone
        System.out.println("No edges: " + ComponentCounter.countComponents(4, new int[][]{}));

        // Fully connected
        System.out.println("Fully connected: " + ComponentCounter.countComponents(3,
            new int[][]{{0,1},{1,2},{0,2}}));

        // Single node
        System.out.println("Single: " + ComponentCounter.countComponents(1, new int[][]{}));
    }
}
TEXT
No edges: 4
Fully connected: 1
Single: 1

What is the time and space complexity?

With path compression and union by rank, each union and find operation is O(alpha(N)), where alpha is the inverse Ackermann function, which is effectively constant for all practical inputs. Processing E edges gives O(E * alpha(N)) total time. Space is O(N) for the parent and rank arrays.

What should a senior engineer know?

Union-Find is the go-to structure for dynamic connectivity problems: counting components, detecting redundant edges, and determining if two nodes are connected. The online property is its main advantage over DFS.

In production at National Bank of India, operations needed to know how many independent settlement networks existed among branches, because each isolated network required its own reconciliation batch. Union-Find maintained that count online as links were added.

JAVA
// Online component tracking in production
UnionFind uf = new UnionFind(branchCount);
int components = branchCount;

for (SettlementLink link : incomingLinks) {
    if (uf.union(link.branchA, link.branchB)) {
        components--;
        System.out.println("Merged. Components now: " + components);
    }
}

Visual Overview

DIAGRAM
  Union-Find Component Counting

  Start: 5 nodes, each its own component
  [0] [1] [2] [3] [4]   components = 5

  Edge (0,1): union → merge
  [0-1] [2] [3] [4]     components = 4

  Edge (1,2): union → merge
  [0-1-2] [3] [4]       components = 3

  Edge (3,4): union → merge
  [0-1-2] [3-4]         components = 2

  Edge (0,2): union → already same set, skip
  [0-1-2] [3-4]         components = 2 (unchanged)
DIAGRAM
  Path Compression

  Before find(0):     After find(0):
  3 (root)            3 (root)
  │                  / | \
  2                 0  1  2
  │
  1
  │
  0

Key Takeaway

Counting connected components with Union-Find is a clean online algorithm. You start with a component counter equal to n, because every node begins as its own isolated set. For each edge, you attempt a union of its endpoints. A successful union merges two previously separate sets and decrements the counter. An edge between two already-connected nodes changes nothing. The final counter value is the number of distinct roots, which is the component count.

Path compression and union by rank together give near-constant amortized time per operation, making the total cost effectively linear in the number of edges. The main advantage over DFS flood-fill is that Union-Find works online: you can process edges as they stream in and always know the current component count without rebuilding an adjacency list.

The key detail is that a redundant edge, one connecting two nodes already in the same set, correctly does nothing to the count. The find calls return the same root, and the union returns false.

In our banking system at National Bank of India, operations needed to track how many independent settlement networks existed among branches, because each isolated network required its own reconciliation batch. Union-Find maintained that count online as new links were added between branches, and redundant links never dropped the count incorrectly.

Remember one sentence: start with n components, decrement on each successful union, and the remainder is the number of connected components.

---

Share
Use ← → arrow keys to navigate