Problem. There are n cities. is_connected[i][j] = 1 if cities i and j are directly connected. A province is a group of
cities connected directly or through other cities, with no city outside the group connected to any inside. Return the number
of provinces.
is_connected = [[1, 1, 0],
[1, 1, 0], → 2 ({0, 1} and {2})
[0, 0, 1]]
It's lesson 11.3's connected components, on a general graph given as an adjacency matrix instead of a grid. The matrix is the input's shape, and it sets the cost: reading it is already O(n²).
ML context. Clustering by links: user accounts linked by shared devices, product listings linked by "same item" predictions, papers linked by citations, entity mentions linked by a coreference model. The clusters are the connected components of the "same as" graph. Links usually arrive over time from a model or from logs, which is where union-find shines (Change A and lesson 11.15).