Union‑Find Explained: Solving the 'Number of Provinces' Problem

Number of Provinces is one of those graph problems that can be solved perfectly well with ordinary traversal, which is exactly why it makes a good union‑find article. We are given an adjacency matrix where isConnected[a][b] tells us whether two cities belong to the same direct network. The task is to count how many disconnected groups exist overall.

If that sounds like connected components, that is because it is.

The honest thing to say straight away is this:

• depth‑first search is probably the simplest answer for this exact problem

So why write the union‑find version? Because the disjoint‑set idea is useful far beyond this one matrix question, and this problem is a friendly place to learn it.

The Direct Dfs Answer

If we only care about solving Number of Provinces cleanly, DFS is excellent.

export const findCircleNum = (isConnected: number[][]): number => {  const cityCount = isConnected.length;  const visited = new Array<boolean>(cityCount).fill(false);  let provinces = 0;  const visit = (city: number): void => {    visited[city] = true;    for (let neighbour = 0; neighbour < cityCount; neighbour += 1) {      if (isConnected[city][neighbour] === 1 && !visited[neighbour]) {        visit(neighbour);      }    }  };  for (let city = 0; city < cityCount; city += 1) {    if (!visited[city]) {      provinces += 1;      visit(city);    }  }  return provinces;};

That is short, readable, and entirely good.

What Union‑Find Changes

Union‑find, also called disjoint‑set union, does not traverse from one node through all its neighbours in the same way. Instead, it keeps track of which items belong to the same set as we discover connections.

It supports two main operations:

• find(x): which set representative does x belong to?
• union(a, b): merge the sets containing a and b

So instead of exploring the graph recursively, we keep folding connected cities into shared groups.

A Practical TypeScript Solution with Union‑Find

class UnionFind {  public readonly parent: number[];  public readonly rank: number[];  public provinceCount: number;  public constructor(size: number) {    this.parent = new Array<number>(size);    this.rank = new Array<number>(size).fill(0);    this.provinceCount = size;    for (let index = 0; index < size; index += 1) {      this.parent[index] = index;    }  }  public find(city: number): number {    if (this.parent[city] !== city) {      this.parent[city] = this.find(this.parent[city]);    }    return this.parent[city];  }  public union(left: number, right: number): void {    const leftRoot = this.find(left);    const rightRoot = this.find(right);    if (leftRoot === rightRoot) {      return;    }    if (this.rank[leftRoot] < this.rank[rightRoot]) {      this.parent[leftRoot] = rightRoot;    } else if (this.rank[leftRoot] > this.rank[rightRoot]) {      this.parent[rightRoot] = leftRoot;    } else {      this.parent[rightRoot] = leftRoot;      this.rank[leftRoot] += 1;    }    this.provinceCount -= 1;  }}export const findCircleNum = (isConnected: number[][]): number => {  const cityCount = isConnected.length;  const unionFind = new UnionFind(cityCount);  for (let city = 0; city < cityCount; city += 1) {    for (let neighbour = city + 1; neighbour < cityCount; neighbour += 1) {      if (isConnected[city][neighbour] === 1) {        unionFind.union(city, neighbour);      }    }  }  return unionFind.provinceCount;};

Why the Upper Triangle is Enough

Because the matrix is symmetric:

• if city a is connected to city b
• then city b is connected to city a

So we do not need to inspect both isConnected[a][b] and isConnected[b][a].

Looping only through:

neighbour = city + 1

avoids duplicate work and keeps the union operations tidy.

What find and union are really doing

At the start, every city is its own province:

• parent of 0 is 0
• parent of 1 is 1
• parent of 2 is 2

If we discover that 0 and 1 are connected, we union their sets. Now they share a root representative.

If we later discover that 1 and 2 are connected, then 2 joins the same group too, even if we never called union(0, 2) directly. That is the point of the structure. It captures connectedness indirectly through group membership.

Why Path Compression and Union by Rank Matter

These two optimisations sound grander than they feel in code.

Path compression means:

• when find walks up to the root, it rewires the nodes it touched so next time the route is shorter

Union by rank means:

• attach the shallower tree under the deeper one so the structure stays flatter

Together, they keep the operations extremely efficient in practice.

You do not need to get lost in the formal amortised‑analysis proof to use them sensibly here. The practical point is enough:

• flatter trees make repeated find calls cheap

Which Solution is Best for This Problem?

For Number of Provinces specifically, I think DFS is the better final answer if the only goal is clarity. The matrix is already there, and a connected‑components traversal reads very naturally.

Union‑find is the more valuable pattern to learn, though, because it generalises well to problems where:

• connections are added over time
• we need repeated connectivity checks
• explicit traversal each time would be awkward

So if I were writing the shortest cleanest accepted solution, I would probably choose DFS. If I were choosing the better article topic and the more reusable mental model, I would choose union‑find.

Where Union‑Find Earns Its Keep More Clearly

This data structure becomes especially handy in problems such as:

• Kruskal's minimum spanning tree
• incremental connectivity queries
• grouping accounts or emails by shared ownership
• merging dynamic components as edges arrive

That is why Number of Provinces is a useful teaching ground. The problem itself does not force union‑find. It simply gives it a clean stage.

Common Mistakes

Scanning the Whole Matrix Twice

The upper triangle is enough once we know the matrix is symmetric.

Forgetting to Reduce the Province Count Only on a Real Merge

If two cities are already in the same set, the province count should not change.

Thinking Union‑Find Stores Every Path Explicitly

It does not. It stores parent links and answers connectivity through representatives.

The Main Lesson Underneath It

Union‑find is useful because it treats connected components as a grouping problem rather than as repeated traversals. That is a different mental model, and it is worth having available even when a DFS would also do the job.

The Pattern to Keep

• DFS is probably the simplest answer for Number of Provinces itself.
• Union‑find is the stronger general‑purpose pattern when connectivity changes or repeated grouping matters.
• find identifies the current group; union merges groups when a new connection is discovered.

This is one of those cases where the most educational answer is not quite the same as the shortest answer. That is exactly why it is worth covering.