Number of Provinces

The problem

Implement `findCircleNum(isConnected)` where `isConnected` is an `n x n` matrix and `isConnected[i][j] === 1` means cities `i` and `j` are directly connected (the matrix is symmetric, and `isConnected[i][i]` is always `1`). Return the number of provinces — the total number of connected components among the `n` cities.

Unlike `countComponents` or `validTree`, the input isn't a list of edges or a pre-built adjacency list — it's a dense grid where every pair's connection is already answered directly, so the usual 'construct a graph first' step doesn't apply.

The approach

Union-Find fits this input shape more naturally than DFS/BFS would: instead of building any adjacency structure first, every `1` found while scanning the matrix is unioned on the spot. Only the upper triangle (`j` starting at `i + 1`) needs scanning, since the matrix is symmetric and the diagonal (`isConnected[i][i]`) is always `1` by definition and would just union a city with itself.

Same DSU primitive as the Union-Find variant of `countComponents`: `provinces` starts at `n`, and every time `find(i) !== find(j)` for a connected pair, merging their roots and decrementing `provinces` collapses two components into one. A `1` between two cities already sharing a root doesn't change the count — it's a redundant connection, not a new merge.

Path compression in `find` (`parent[x] = parent[parent[x]]`) keeps repeated lookups cheap, though here the `O(n^2)` matrix scan itself dominates the runtime, not the DSU operations — a contrast with edge-list input, where the graph's size (`V + E`) sets the pace instead.

The solution

class Solution {
    /**
     * @param {number[][]} isConnected
     * @return {number}
     */
    findCircleNum(isConnected) {
        const n = isConnected.length;
        const parent = Array.from({ length: n }, (_, i) => i);
        let provinces = n;

        const find = (x) => {
            while (parent[x] !== x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };

        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                if (isConnected[i][j] === 1) {
                    const rootI = find(i);
                    const rootJ = find(j);
                    if (rootI !== rootJ) {
                        parent[rootI] = rootJ;
                        provinces--;
                    }
                }
            }
        }

        return provinces;
    }
}

Time O(n^2)Space O(n)