Number of Provinces
WHAT IT SAYS
Given an adjacency matrix of cities where connections are transitive friendships, count the groups of directly-or-indirectly connected cities.
WHAT IT'S REALLY ASKING
"One traversal launched from any city consumes its ENTIRE province — everything reachable, in one exhaustion. So don't count cities or connections. Count how many times you're forced to RESTART: each launch from an unvisited city is a certificate that a brand-new province just began."
Compute the full reachability closure
O(n^3) time, O(n^2) spaceTwo cities share a province iff one reaches the other, so compute all-pairs reachability — Floyd-Warshall style transitive closure — then group cities by identical reachability sets and count the groups.
WHERE THE WORK IS WASTED — The closure answers n^2 questions — 'does i reach j?' for every pair — when the problem needs only a partition into groups, which contains far less information. Every pair WITHIN a province gets its connectivity individually certified, though one shared witness (the traversal that swept them all up together) certifies all of them at once. You are computing the complete relation to read off its equivalence classes, when the classes can be enumerated directly by exhausting one at a time.
Exhaust one component per launch; the counter counts launches.
A province is a connected component: a maximal set where every member reaches every other. Two properties of 'maximal' do all the work. First, a traversal from any seed city visits exactly its component — no less, because DFS/BFS follows every edge out of every reached node until none remain unexplored (reachability is exhausted); no more, because every visited node was reached BY a path from the seed, so it belongs. One launch, one complete province, marked in the visited set. Second, components partition the cities — disjoint, covering. Disjointness is why the visited set never lies: a city marked by a previous launch can never belong to the current province, so skipping visited cities skips exactly the already-counted. Coverage is why the outer loop is complete: sweep the cities in order, and every province gets discovered at its lowest-indexed member — the first member the sweep touches while it is still unvisited. So the algorithm is: for each city, if unvisited, increment the counter and exhaust its component. The count of LAUNCHES equals the count of provinces — the traversal isn't computing anything per se; each launch IS the discovery event, and the counter is counting discoveries. Total cost: every city visited once across all launches combined (the partition guarantees no overlap), every matrix row scanned once — O(n^2), which is just reading the input. The alternative worth knowing because it wins under different access patterns: Union-Find. Process each edge by uniting its endpoints; start with n singleton sets; each successful union reduces the set count by one. The answer is n minus successful unions. Same result, but incremental — if edges ARRIVE OVER TIME and the count is queried between arrivals, union-find updates in near-O(1) per edge while traversal would recompute from scratch. Static graph: traverse. Dynamic edges: union.
Sweep, launch on unvisited, exhaust
O(n^2) time — the matrix must be read — O(n) space beyond itvisited = boolean array. For each city i: if not visited, count++, then DFS/BFS from i marking every reachable city (scan row i of the matrix for neighbours, recurse). Return count. Union-Find variant: for each edge (i, j), union; answer is n minus successful merges.
One Launch, One Component
YOU'LL SEE IT AGAIN WHEN
- The question asks for a COUNT or PARTITION of maximal connected groups, not for any pairwise reachability facts.
- An exhaustive traversal from any seed provably consumes exactly one group — maximality guarantees no leakage between groups.
- Edges arrive incrementally or merges are queried mid-stream — the signal to switch from traversal-counting to union-find.