Связные компоненты и заливка
Подсчитывайте острова и размечайте области
«Связные компоненты и заливка» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Что такое компонента связности
Связная компонента — это группа вершин, из каждой из которых можно добраться до любой другой. Граф может содержать несколько отдельных групп. 🧩
Подсчёт компонент
Чтобы подсчитать компоненты, выполните обход из каждой непосещённой вершины. Каждый новый старт отмечает одну новую целую группу.
Перебор всех вершин
Пройдите по вершинам от 1 до n. Найдя всё ещё непосещённую вершину, вы обнаружите новую компоненту для исследования.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1Один обход на каждую группу
Этот внутренний BFS или DFS отмечает всю компоненту как посещённую, поэтому при следующем проходе внешний цикл пропускает её.
Таблицы тоже являются графами
Двумерная таблица — это скрытый граф: каждая ячейка является вершиной, соединённой с соседями. Это позволяет применять классическую идею заливки области. 🗺️
Четыре направления
Из ячейки обычно переходят вверх, вниз, влево и вправо. Храните эти перемещения как векторы направлений, чтобы код оставался понятным.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Оставайтесь внутри сетки
Перед переходом проверьте, что новая строка и столбец находятся в пределах границ. Если пропустить эту проверку, возникнут ошибки индексации или неправильные ответы.
if 0 <= nr < rows and 0 <= nc < cols:
passЗаливка одной области
Заливка области начинается с одной ячейки и распространяется на все соединённые ячейки того же типа — совсем как инструмент заливки.
Подсчёт островов
Чтобы посчитать острова, просмотрите сетку: при обнаружении новой ячейки суши выполните заливку всего острова и увеличьте счётчик на единицу.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Разметка областей
Во время заливки можно сохранить метку для каждой ячейки. Позже Вы сразу будете знать, к какой области относится любая ячейка.
Линейная зависимость от размера сетки
Каждая ячейка посещается один раз, поэтому заливка области на сетке работает за O(число строк × число столбцов). Это с запасом укладывается в ограничения соревнований.
Быстрая проверка
Как посчитать компоненты связности?
Повторение
Вы считаете компоненты, выполняя обход от каждой непосещённой вершины, а для сеток используете заливку области, чтобы размечать области и считать острова. 🎉
Часто задаваемые вопросы
Урок «Связные компоненты и заливка» бесплатный?
Да — полный текст урока «Связные компоненты и заливка» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Связные компоненты и заливка»?
Подсчитывайте острова и размечайте области Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Связные компоненты и заливка»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Списки смежности из входных данных
- BFS для кратчайших невзвешенных путей
- DFS, рекурсия и итеративные стеки
- Связные компоненты и заливка