Выбор ответа Junior Графы: BFS и DFS спрашивают часто обновлено
Число островов
Вопрос
Сетка из "1" (суша) и "0" (вода). Как посчитать острова?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: На каждой непосещённой суше запускать DFS/BFS и увеличивать счётчик островов. Каждый запуск обхода закрашивает одну компоненту связности целиком, значит число запусков равно числу островов.
Варианты ответа
- На каждой непосещённой суше запускать DFS/BFS и увеличивать счётчик острововправильный ответ
- Посчитать все
"1"в сетке: каждая клетка суши это отдельный остров - Отсортировать строки сетки и посчитать группы подряд идущих
"1" - Бинпоиском по строкам найти границы суши и посчитать отрезки
Разбор
Каждый запуск обхода закрашивает одну компоненту связности целиком, значит число запусков равно числу островов. O(R · C).
- Число единиц это площадь суши, а не число островов.
- Сортировка и бинпоиск не находят связность.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.