323. Number of Connected Components in an Undirected Graph

RUN IT Union-Find each edge, count remaining roots

TYPESCRIPT The solution, annotated

function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x: number): number {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path compression (halving)
      x = parent[x];
    }
    return x;
  }

  function union(a: number, b: number): boolean {
    const ra = find(a);
    const rb = find(b);
    if (ra === rb) return false; // already connected
    parent[rb] = ra;             // merge rb's tree under ra
    return true;
  }

  let components = n;
  for (const [a, b] of edges) {
    if (union(a, b)) components--; // successful merge = one fewer component
  }
  return components;
}

Reading it block by block

INTERVIEWFollow-ups they'll ask

• "What if you need the actual groups, not just the count?" After all unions, group nodes by their root: find(i) as the bucket key in a Map.
• "Graph Valid Tree variant?" A graph on n nodes is a valid tree iff it has exactly n-1 edges, no cycle, and is fully connected — equivalently, Union-Find reports exactly 1 component and every edge is a successful merge.
• "Redundant Connection?" Process edges in order; the first edge where find(a) === find(b) before the union is the redundant one (it closes a cycle).
• "Union by rank vs path compression?" Adding union-by-rank (always merge the shorter tree under the taller) gives the full O(α(n)) guarantee; path halving alone is O(log* n) — still practically constant and simpler to code under pressure.
• "What if edges arrive as a stream?" Union-Find is the only classic structure that handles fully-online incremental connectivity; BFS/DFS must re-traverse the whole graph after each new edge.

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

const parent = Array.from({ length: n }, (_, i) => i);

function find(x: number): number {
  while (parent[x] !== x) {
    parent[x] = parent[parent[x]]; // path halving
    x = parent[x];
  }
  return x;
}

let components = n;
for (const [a, b] of edges) {
  const ra = find(a), rb = find(b);
  if (ra !== rb) {
    parent[rb] = ra;
    components--;
  }
}
return components;

FLASHCARDS Tap to flip