Где применяется
1. Задача
У тебя есть класс учеников и список, кто с кем дружит. Одни дружбы цепляются друг за друга и собирают большую компанию. Несколько учеников дружат втроём, в стороне от остальных. Один ученик не знает никого. Вопрос: сколько в классе отдельных кругов друзей?
Так же устроены подсчёт островов на карте и поиск несвязанных между собой кластеров в сети. У тебя есть граф (точки, соединённые линиями), и он может состоять из нескольких кусков. Между кусками нет ни одного ребра. Нужно узнать, сколько этих кусков.
В уроках про BFS и DFS ты обходил граф от одного старта. Один обход доходит до всех узлов своего куска и ни до одного узла чужого. Значит, кусков столько, сколько обходов нужно, чтобы побывать в каждом узле.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитcountComponents(7, {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3, 5], 5: [4], 6: []})Считаем отдельные группы среди 7 вершин. Одно множество visited живёт весь запуск и не сбрасывается.
Как узнать
Эти слова в условии значат этот паттерн
- посчитать число отдельных групп/островов/кластеров
- граф может быть несвязным
- сколько связных частей
- круги друзей
- разметить связные области
Похоже, но не то
- Обход графа BFS / DFS (Graph BFS / DFS)
Это сам обход. Здесь описан цикл, запускающий по одному обходу на группу.
- Система непересекающихся множеств (Union-find (disjoint set))
Она отвечает, пока рёбра ещё приходят. Заливке нужен весь граф сразу.
- Проверка двудольности (раскраска в два цвета) (Bipartite check (two-coloring))
Раскраска ведёт тот же обход, но несёт цвет. Она отвечает на другой вопрос.
- Топологическая сортировка (алгоритм Кана) (Topological sort (Kahn's algorithm))
Упорядочиванию нужны направленные рёбра без циклов. Компоненты считают любое ребро ненаправленным.
V вершин и E рёбер дают в сумме O(V + E). Каждую вершину посещает ровно один обход.
На LeetCode
Задачи, где нужно посчитать отдельные группы, например острова, круги друзей или сети. Пройди по всем узлам, и каждый ещё не посещённый узел начинает новую группу, которую один обход отмечает целиком.
countComponents из урока, только граф задан матрицей смежности.
Каждая непосещённая клетка суши начинает новый остров, а обход отмечает всю его сушу.
Тот же цикл, только каждый обход возвращает размер своей группы, и ты оставляешь наибольший.
Обходи каждый остров grid2 и считай его, только если каждая его клетка есть суша и в grid1.