Union find

Connected Components

syntax

Run BFS or DFS from each unvisited node.
Each run discovers one connected component.
Count the number of runs = number of components.

example

// JavaScript
function countComponents(n, edges) {
  const graph = new Map();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u).push(v);
    graph.get(v).push(u);
  }
  const visited = new Set();
  let components = 0;
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      components++;
      const queue = [i];
      visited.add(i);
      while (queue.length) {
        const node = queue.shift();
        for (const nb of graph.get(node)) {
          if (!visited.has(nb)) {
            visited.add(nb);
            queue.push(nb);
          }
        }
      }
    }
  }
  return components;
}

# Python
def count_components(n, edges):
    from collections import defaultdict, deque
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    components = 0
    for i in range(n):
        if i not in visited:
            components += 1
            queue = deque([i])
            visited.add(i)
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if nb not in visited:
                        visited.add(nb)
                        queue.append(nb)
    return components

output

n=5, edges=[[0,1],[1,2],[3,4]] → 2 components ({0,1,2} and {3,4})

Note Time O(V + E), Space O(V). Alternative: Union-Find achieves the same result and is better for dynamic connectivity. This pattern is the basis for 'number of islands' and 'number of provinces' problems.

Pattern: Union-Find (Disjoint Set)

DSA · Common Patterns Summary

syntax

Track connected components efficiently.
Two operations:
- find(x): return the root/representative of x's set
- union(x, y): merge the sets containing x and y

Optimizations: path compression + union by rank

example

// JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

# Python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

output

uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 3)
uf.find(0) == uf.find(3) → True (same component)

Note With both optimizations, operations are nearly O(1) amortized (technically O(alpha(n)) inverse Ackermann). Perfect for: connected components, redundant connections, accounts merge, minimum spanning tree (Kruskal's). Union returns false when already connected — useful for cycle detection.

DSAInterview Prep