Код Middle Графы: BFS и DFS обновлено
Число связных групп
Условие
Матрица смежности n×n: m[i][j] === 1 означает связь. Сколько связных групп?
Примеры
countProvinces([[1, 1, 0], [1, 1, 0], [0, 0, 1]]) // 2
countProvinces([[1, 0], [0, 1]]) // 2
countProvinces([]) // 0
Как подойти
Тот же счёт компонент связности, что и в задаче об островах, только граф задан матрицей смежности, а не сеткой. Полезно узнавать одну задачу в разных формулировках. Альтернатива - система непересекающихся множеств, она выигрывает при динамическом добавлении рёбер.
Подсказки: 2
- Каждый непосещённый узел начинает новую группу.
- Внутри группы обходим всё достижимое и помечаем.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.