Почему это работает
- Сначала каждый город — отдельная провинция, а прямая связь сливает две провинции, которых касается, поэтому в конце в провинции ровно те города, что достижимы друг из друга.
- Счётчик уменьшается, только если корни разные. Связь внутри одной провинции, как 1–2 здесь, ничего не меняет, поэтому города не считаются дважды.
- Матрица симметрична, а её диагональ говорит лишь, что город связан сам с собой, поэтому хватает единиц над диагональю.
Сложность
Время O(n² · h): просматриваем все пары матрицы, а каждая единица — это два find глубиной с дерево, здесь до n и почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее. Память O(n) на parent.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗