Typorithm · medium

Connected Components

count-componentsunion-findcomponentsmergecounting

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Connected Components

Union-Find

Start with n components and subtract one for every edge whose union actually merges two different sets.

The number of connected components starts at n, with each node isolated.

Processing each edge, a successful union — joining two distinct sets — reduces the count by one.

Edges within an already-connected set return false and leave the count unchanged.

Begin with n components.

Decrement only on a real merge.

Redundant edges change nothing.

function countComponents(n, edges) {
  const uf = new UnionFind(n);
  let components = n;

  for (const [a, b] of edges) {
    if (uf.union(a, b)) {
      components -= 1;
    }
  }

  return components;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Start separate

Every node begins as its own component.

let components = n

2. Merge on success

A successful union joins two previously separate components.

if (uf.union(a, b)) {

3. One fewer group

Each real merge reduces the component count by one.

components -= 1

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.