Standard Bar Graphs · Traversal Problems O(n^2) · O(n)
A courier network's control room keeps an n x n handshake table: row i, column j shows whether depot i can hand parcels directly to depot j. Two depots belong to the same cluster when a chain of handshakes — however long — links them. Dispatch needs the number of separate clusters, because each cluster needs its own coordinator.
Input: An n x n binary matrix isConnected where isConnected[i][j] is 1 if depot i and depot j are directly linked.
Output: Return the number of connected clusters (provinces).
1 <= n <= 10^3isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]Input: {"isConnected":[[1,1,0],[1,1,0],[0,0,1]]}
Output: 2
Depots 0 and 1 shake hands with each other; depot 2 stands alone.
Input: {"isConnected":[[1,0,0],[0,1,0],[0,0,1]]}
Output: 3
No cross-links at all — every depot is its own province.