Number of Provinces

Средняя№547

Есть n городов и квадратная матрица isConnected: isConnected[i][j] равно 1, если города i и j связаны напрямую, и 0, если нет. Провинция — группа городов, которые достижимы друг из друга напрямую или через другие города. Нужно посчитать провинции. Наш пример: [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1] → 2.

547 Number of ProvincesРазбор · 1×

Пример: [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]: пары 0–1, 0–2, 1–2 и 3–4. Третья пара ничего не сливает: у 1 и 2 уже общий корень 0.

01234011100111100211100300011400011isConnected012340011223344parent
смотрим сейчаскорень провинцииединица уже учтенана диагонали и под ней: пропускаем

Каждый город — сам себе корень

01/53
сначала · назад · пуск · шаг
Скорость
1function findCircleNum(isConnected):
2 parent = [0, 1, ..., n - 1]
3 provinces = n
4 for each pair i < j with isConnected[i][j] == 1:
5 rootI = find(i)
6 rootJ = find(j)
7 if rootI is not rootJ:
8 parent[rootJ] = rootI
9 provinces = provinces - 1
10 return provinces
11
12function find(x):
13 while parent[x] is not x:
14 x = parent[x]
15 return x
состояние
parent
[0, 1, 2, 3, 4]
provinces
–
i
–
j
–
rootI
–
rootJ
–
x
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Сначала каждый город — отдельная провинция, а прямая связь сливает две провинции, которых касается, поэтому в конце в провинции ровно те города, что достижимы друг из друга.
  2. Счётчик уменьшается, только если корни разные. Связь внутри одной провинции, как 1–2 здесь, ничего не меняет, поэтому города не считаются дважды.
  3. Матрица симметрична, а её диагональ говорит лишь, что город связан сам с собой, поэтому хватает единиц над диагональю.

Сложность

Время O(n² · h): просматриваем все пары матрицы, а каждая единица — это два find глубиной с дерево, здесь до n и почти константа, если перевешивать на корень и подвешивать меньшее дерево под большее. Память O(n) на parent.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.