Число провинций
Система непересекающихся множеств (DSU)
Легкая
Дана матрица смежности is_connected размера n x n, где is_connected[i][j] = 1, если города i и j связаны напрямую. Провинция - группа городов, связанных прямо или косвенно. Посчитайте число провинций с помощью Union-Find.
Сигнатура функции
count_provinces(is_connected: list[list[int]]) -> int
Примеры
| Вход | Ожидаемый результат |
|---|
| [[[1, 1, 0], [1, 1, 0], [0, 0, 1]]] | 2 |
| [[[1, 0, 0], [0, 1, 0], [0, 0, 1]]] | 3 |
1решили
1пытались
100%успешность
Войдите, чтобы решить →