Number of Provinces

Problem (restated)

n cities with isConnected matrix. A province is a connected group. Return number of provinces.

Intuition

Union connected pairs; answer is component count.

Approaches

export function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length;
  const p = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x]!)));
  let comp = n;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i]![j] === 1) {
        const a = find(i), b = find(j);
        if (a !== b) {
          p[b] = a;
          comp--;
        }
      }
    }
  }
  return comp;
}

export function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length;
  const p = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (p[x] === x ? x : (p[x] = find(p[x]!)));
  let comp = n;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i]![j] === 1) {
        const a = find(i), b = find(j);
        if (a !== b) {
          p[b] = a;
          comp--;
        }
      }
    }
  }
  return comp;
}

Template connection

Union-Find components.

Reflection

• Union i and j when isConnected[i][j] == 1. The answer is how many components remain. The diagonal is a city with itself.
• A second union onto the same root does not shrink the count. The matrix is symmetric.
• n = 1 answers 1. No edges answers n. Everyone connected answers 1.