Number of Provinces

Пройдитесь по городам по порядку. Если вы встречаете город, который не был отмечен ни одним предыдущим поиском, он не может принадлежать провинции, которую вы уже посчитали, потому что каждый поиск отмечает всю свою провинцию. Поэтому увеличьте счётчик на единицу, а затем отметьте все города, до которых можно добраться из этого города.

Чтобы найти их, используйте стек. Извлеките город, прочитайте его строку матрицы и добавьте в стек каждый город, у которого в этой строке стоит 1 и который ещё не отмечен, отмечая его при добавлении в стек. Во втором примере поиск из города 0 добавляет в стек город 1, а строка города 1 затем добавляет город 2, хотя в строке 0 для города 2 стоит 0. Именно такой переход по строкам позволяет находить города, связанные только через другие города.

Каждый город извлекается один раз, и при его извлечении читаются n элементов его строки, поэтому общее время — O(n²): вы читаете матрицу один раз. Для отметок и стека требуется не более n городов, поэтому дополнительная память — O(n).

Рекурсивный поиск выглядит аккуратнее, но в провинции, вытянутой в длинную линию, вызовы вкладываются друг в друга по одному на каждый город. При n = 150 это безопасно; тот же код на графе с 10^5 узлами переполнит стек вызовов, поэтому стоит придерживаться привычки использовать явный стек.

Перевернём вопрос. Начнём с n провинций, по одной на город. Каждая 1 в матрице означает, что два города связаны: если они всё ещё в разных группах, объединим группы, и счёт уменьшится на единицу. После последней дороги счёт и будет ответом. Достаточно рассмотреть элементы выше главной диагонали, потому что матрица симметрична, а диагональ связывает город с самим собой. Во втором примере счёт начинается с 5. Единица в (0, 1) объединяет города 0 и 1 (остаётся 4), а единица в (1, 2) обнаруживает, что город 1 относится к группе города 0, и добавляет к ней город 2 (остаётся 3). У городов 3 и 4 выше диагонали нет единиц, поэтому ответ — 3.

Структура «объединение-поиск», также называемая системой непересекающихся множеств, хранит каждую группу в виде дерева. parent[c] указывает на родительский узел на один уровень выше, а город в корне, родителем которого является он сам, — это корень группы. Два города находятся в одной группе тогда и только тогда, когда find поднимается от обоих к одному и тому же корню. Чтобы объединить две группы, укажем один корень как родителя другого.

Два правила помогают сохранять деревья плоскими. Объединение по рангу подвешивает более короткое дерево под более высоким, поэтому дерево высоты h содержит не менее 2^h городов, а длина любого пути не превышает log n. Сжатие пути идёт дальше: как только find находит корень, он направляет каждый пройденный город прямо к этому корню, поэтому при следующем поиске от любого из них потребуется один шаг. Без любого из этих правил объединение городов длинной цепочки в неудачном порядке создаёт дерево в виде единственного пути, и каждый вызов find проходит O(n) шагов.

При использовании обоих правил амортизированная стоимость каждого вызова find составляет O(α(n)), где α — обратная функция Аккермана, которая не превышает 4 для любого n, помещающегося в компьютере. Чтение матрицы всё ещё требует O(n²), поэтому такова общая сложность, а для массивов parent и rank требуется O(n) памяти. Эта структура особенно полезна, когда дороги появляются по одной: она обновляет счёт после каждой новой дороги, не выполняя повторный поиск.