Why it works
- Every city starts as a province of its own, and a direct link merges the two provinces it touches, so in the end a province holds exactly the cities that reach each other.
- The count drops only when the two roots differ. A link inside one province, like 1–2 here, changes nothing, so cities are never counted twice.
- The matrix is symmetric and its diagonal says only that a city is linked to itself, so the 1s above the diagonal are enough.
Complexity
Time O(n² · h): all pairs of the matrix are looked at, and each 1 costs two finds as deep as the trees, which is up to n here and almost a constant with re-hanging on the root and the smaller tree under the bigger. Memory O(n) for parent.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗