Number of Provinces

Minimum Size Subarray Sum

Sort Colors

Count how many disconnected city groups exist in an undirected connectivity matrix.

You are given an `n x n` matrix `isConnected` where `isConnected[i][j]` is `1` when city `i` and city `j` are directly connected and `0` otherwise. A province is a group of cities that are connected directly or through other cities. Return how many provinces exist in total.

## Example
```
Input: {"isConnected":[[1,1,0],[1,1,0],[0,0,1]]}
Output: 2
```

**Constraints**
- 1 <= isConnected.length <= 200
- `isConnected[i].length == isConnected.length`
- `isConnected[i][i] == 1`
- `isConnected[i][j] == isConnected[j][i]`

**Follow-up**
How would you support incremental connection updates without recomputing from scratch?

- `isConnected` is an n x n adjacency matrix over directly-connected cities; "province" means a connected component under the transitive closure of that direct-connection relation (if A-B and B-C are both direct connections, A and C are in the same province even with no direct A-C entry).
- The answer is just the number of connected components in this graph.

Understand the Goal

- Disjoint-set union (union-find): start with every city in its own set, then union the two endpoints of every direct connection. The final answer is the number of distinct sets remaining.
- Path compression (flattening each `find` chain toward the root as you traverse it) and union by rank (attaching the shorter tree under the taller one) keep the amortized cost of each operation nearly constant, which is why DSU beats a plain DFS/BFS-per-node only in code simplicity here, not asymptotics — but it generalizes better to the "incremental connection updates" follow-up.

Choose the Core Pattern

- Initialize `parent[i] = i` for every city and a running `provinces` counter at `n` (every city starts as its own province).
- `find(x)` walks parent pointers to the root, compressing the path along the way so future lookups are faster.
- `union(a, b)`: find both roots; if they're already equal, this connection is redundant — do nothing and report no merge happened. Otherwise attach the lower-rank root under the higher-rank root (bumping rank on a tie), and report that a merge happened.
- Scan only the upper triangle of the matrix (`col > row`, since it's symmetric) and call `union` for every `isConnected[row][col] == 1`; decrement `provinces` **only** when `union` reports an actual merge (roots were different) — unioning two cities already in the same province must not double-decrement.

Build the Algorithm

- All cities connected to each other (all 1s): every union after the first in a component reports "already merged," so `provinces` ends at 1.
- No city connected to any other except itself (identity matrix): no union ever succeeds, so `provinces` stays at `n`.
- A single city (`n == 1`): the loop over pairs never runs, and the answer is correctly 1.
- A chain like 1-2, 2-3 (but no direct 1-3 entry): after unioning (1,2) and (2,3), `find(1) == find(3)` transitively through path compression, even though the matrix has no direct 1-3 edge.