Number of Islands: подсчёт островов на сетке через DFS, BFS и DSU

Коротко

Number of Islands (LeetCode 200) — одна из самых частых задач на графы на собеседованиях. При этом слово «граф» в условии не встречается: дана обычная матрица символов. Вся сложность задачи в том, чтобы увидеть граф там, где его явно не нарисовали. Дальше работает стандартный обход, о котором подробно написано в статье про BFS и DFS. Здесь разберём, как этот обход ложится на сетку, где он ломается и какие задачи решаются тем же кодом почти без изменений.

Условие

Дана сетка grid размером $m \times n$ из символов '1' (суша) и '0' (вода). Островом считается группа клеток суши, соединённых по горизонтали или вертикали. Диагональные соседи не считаются. Всё за пределами сетки — вода. Нужно вернуть количество островов.

Вход:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Выход: 3

Левый верхний квадрат 2×2 — первый остров, одиночная клетка в центре — второй, пара клеток справа внизу — третий. Обратите внимание на клетки (2, 2) и (3, 3): они касаются углами, но это два разных острова, потому что диагональ не связывает.

Ограничения на LeetCode: $1 \le m, n \le 300$. Значит, в сетке до 90 000 клеток. Это число ещё понадобится, когда речь пойдёт о глубине рекурсии.

Как увидеть граф

Сформулируем задачу в терминах графа:

• вершины — клетки со значением '1';
• рёбра — пары соседних по стороне клеток суши;
• остров — компонента связности, то есть максимальное множество вершин, между любыми двумя из которых есть путь.

Подсчёт компонент связности — классическая задача: перебираем вершины, и если вершина ещё не посещена, запускаем из неё обход, который пометит всю её компоненту. Число запусков обхода и есть ответ.

Строить граф явно (список смежности) не нужно. Соседи клетки (r, c) вычисляются на лету: (r+1, c), (r-1, c), (r, c+1), (r, c-1). Надо только проверить, что сосед не вышел за границы сетки. Так экономится и память, и код.

Отдельный массив visited тоже не обязателен: посещённую сушу можно превратить в воду. Этот приём называют «затоплением» (flood fill). Он портит входные данные, поэтому на собеседовании стоит сказать об этом вслух и спросить, можно ли менять grid. Если нельзя — заведите visited размером $m \times n$ или множество координат, асимптотика не изменится.

Решение 1: рекурсивный DFS

Самый короткий и самый популярный вариант:

def num_islands_rec(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Функция sink сначала проверяет, что клетка в пределах сетки и это суша, затем топит её и рекурсивно идёт к четырём соседям. Внешний цикл находит «новые» острова: если клетка всё ещё '1', значит, ни один предыдущий обход до неё не дотянулся.

Важная деталь: клетка помечается до рекурсивных вызовов. Если поменять порядок, обход начнёт ходить по кругу между соседями и никогда не остановится.

Сложность. Каждая клетка топится ровно один раз, и из каждой мы проверяем четырёх соседей. Получаем $O(m \cdot n)$ по времени. Внешний цикл тоже $O(m \cdot n)$, итог не меняется. Памяти уходит столько, какова максимальная глубина рекурсии, а она в худшем случае равна размеру острова, то есть $O(m \cdot n)$.

Почему рекурсия падает

Последняя фраза — не формальность. Возьмём сетку, целиком состоящую из суши. sink первым делом идёт вниз, потом снова вниз, доходит до нижней границы, сворачивает вбок и так далее. Цепочка незавершённых вызовов может вытянуться почти на всю сетку.

В CPython по умолчанию лимит глубины рекурсии — 1000 кадров (sys.getrecursionlimit()). Проверка на практике:

grid = [['1'] * 30 for _ in range(30)]
print(num_islands_rec(grid))  # 1

grid = [['1'] * 40 for _ in range(40)]
num_islands_rec(grid)  # RecursionError: maximum recursion depth exceeded

Сетка 40×40 — это всего 1600 клеток, а ограничения задачи допускают 90 000. В Java и C++ лимита в виде числа кадров нет, зато есть размер стека потока (часто от 512 КБ до 8 МБ в зависимости от платформы и настроек). Глубина в десятки тысяч вызовов его тоже может исчерпать, и вместо исключения вы получите StackOverflowError или просто аварийное завершение процесса.

Есть ли решение на LeetCode, которое проходит с рекурсией? Часто да: тесты не всегда содержат худший случай. Но на собеседовании полезно самому сказать: «Рекурсия здесь может уйти на глубину $m \cdot n$, на большой сетке это переполнение стека, поэтому сделаю итеративно». Это ровно тот вопрос, который интервьюер задаст следом. Подробнее о том, как устроен стек вызовов, — в статье про рекурсию.

Можно ли просто поднять лимит

В Python можно, но аккуратно:

import sys
import threading

sys.setrecursionlimit(1_000_000)
threading.stack_size(512 * 1024 * 1024)

result = []
grid = [['1'] * 300 for _ in range(300)]
worker = threading.Thread(target=lambda: result.append(num_islands_rec(grid)))
worker.start()
worker.join()
print(result)  # [1]

Одного setrecursionlimit мало: лимит снимается, но стек основного потока остаётся прежним, и интерпретатор упадёт уже на уровне операционной системы, без понятной ошибки. Поэтому рекурсию запускают в отдельном потоке с увеличенным стеком. Так делают в олимпиадном программировании, но в продакшен-коде и на интервью это выглядит как костыль. Проще переписать обход на явный стек.

Решение 2: итеративный DFS

Заменяем стек вызовов на обычный список:

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def num_islands_stack(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'
            stack = [(r, c)]
            while stack:
                cr, cc = stack.pop()
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        stack.append((nr, nc))
    return count

Кортеж DIRS с четырьмя направлениями — стандартный приём для задач на сетках: вместо четырёх почти одинаковых проверок один цикл. Если по условию соседи считаются и по диагонали, достаточно добавить ещё четыре пары.

Клетку топим при добавлении в стек, а не при извлечении. Если помечать при извлечении, одна и та же клетка успеет попасть в стек несколько раз (от разных соседей). Ответ останется верным, но стек раздуется, а на плотной сетке это заметно.

Сетка 300×300 из единиц обрабатывается без проблем. Тот же код на JavaScript спокойно переваривает и 1000×1000:

function numIslands(grid) {
  const rows = grid.length
  const cols = grid[0].length
  let count = 0
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue
      count++
      grid[r][c] = '0'
      const stack = [[r, c]]
      while (stack.length) {
        const [cr, cc] = stack.pop()
        for (const [dr, dc] of [
          [1, 0],
          [-1, 0],
          [0, 1],
          [0, -1],
        ]) {
          const nr = cr + dr
          const nc = cc + dc
          if (
            nr >= 0 &&
            nr < rows &&
            nc >= 0 &&
            nc < cols &&
            grid[nr][nc] === '1'
          ) {
            grid[nr][nc] = '0'
            stack.push([nr, nc])
          }
        }
      }
    }
  }
  return count
}

Решение 3: BFS

Достаточно заменить стек на очередь:

from collections import deque


def num_islands_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'
            queue = deque([(r, c)])
            while queue:
                cr, cc = queue.popleft()
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))
    return count

Для подсчёта островов порядок обхода не важен: и DFS, и BFS пометят ровно ту же компоненту. Разница в двух вещах.

• Память. В очереди BFS лежит «фронт волны» — клетки на одном расстоянии от старта. На типичных картах он заметно короче, чем стек итеративного DFS на плотной суше, но в худшем случае обе структуры занимают $O(m \cdot n)$. На практике оба варианта укладываются в лимиты.
• Расширяемость. BFS обходит клетки по слоям, то есть в порядке расстояния от старта. Для подсчёта островов это не нужно, но в соседних задачах (Rotting Oranges, кратчайший путь в бинарной матрице, Walls and Gates) без этого не обойтись. Поэтому многие сразу пишут BFS: потом проще перестроить решение под follow-up.

deque здесь обязательна. list.pop(0) сдвигает весь список и стоит $O(k)$, на большой сетке это превращает линейный алгоритм в квадратичный.

Решение 4: система непересекающихся множеств

Третий способ вообще не делает обход. Каждая клетка суши — отдельное множество, соседние клетки суши объединяются. Количество множеств в конце — ответ. Структура подробно разобрана в статье про DSU, здесь — компактная версия со сжатием путей и объединением по размеру:

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = 0

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1


def num_islands_dsu(grid):
    rows, cols = len(grid), len(grid[0])
    dsu = DSU(rows * cols)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            dsu.components += 1
            if r > 0 and grid[r - 1][c] == '1':
                dsu.union(r * cols + c, (r - 1) * cols + c)
            if c > 0 and grid[r][c - 1] == '1':
                dsu.union(r * cols + c, r * cols + c - 1)
    return dsu.components

Несколько деталей:

• Клетка (r, c) превращается в номер r * cols + c. Это стандартный способ уложить двумерную сетку в одномерный массив.
• Счётчик components растёт на единицу для каждой клетки суши и уменьшается при каждом успешном объединении. Если две клетки уже в одном множестве, union ничего не делает и счётчик не трогает.
• Достаточно смотреть на соседей сверху и слева. Мы идём по сетке построчно, поэтому соседи снизу и справа ещё впереди: когда до них дойдёт очередь, они сами посмотрят вверх и влево. Каждое ребро обрабатывается ровно один раз.
• find итеративный, поэтому проблема глубины рекурсии сюда не переносится.
• Сетку решение не портит.

Сложность — $O(m \cdot n \cdot \alpha(m \cdot n))$, где $\alpha$ — обратная функция Аккермана, на практике не больше 4. Памяти $O(m \cdot n)$ на массивы parent и size, причём выделяются они на всю сетку, даже если суши почти нет.

Зачем DSU, если есть обход

Для статичной сетки DSU не быстрее и пишется дольше. Его настоящая сила — в задаче Number of Islands II (LeetCode 305): сетка изначально из воды, и приходят запросы «в клетке (r, c) появилась суша». После каждого запроса нужно вернуть текущее число островов. Перезапускать обход на каждый запрос — это $O(k \cdot m \cdot n)$. С DSU каждый запрос — это одно добавление и до четырёх объединений, то есть почти $O(1)$. Если на собеседовании после базовой задачи спрашивают «а если клетки добавляются онлайн?», ждут именно DSU.

Сравнение подходов

Если менять сетку нельзя, у DFS и BFS появляется ещё $O(mn)$ на visited. Асимптотика та же.

Вариация: Max Area of Island

LeetCode 695: та же сетка (но из чисел 0 и 1), нужно вернуть площадь самого большого острова. Если островов нет, ответ 0.

Меняется одна вещь: обход не просто топит остров, а считает, сколько клеток утопил.

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            grid[r][c] = 0
            stack = [(r, c)]
            area = 0
            while stack:
                cr, cc = stack.pop()
                area += 1
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))
            best = max(best, area)
    return best

area увеличивается при извлечении из стека: каждая клетка попадает в стек ровно один раз (помечаем при добавлении), значит, и посчитается ровно один раз. На примере из условия LeetCode функция возвращает 6.

В DSU-версии площадь бесплатно хранится в массиве size: ответ — максимум size[find(x)] по всем клеткам суши. Вот ещё одна причина делать объединение по размеру, а не по рангу.

Типичная ошибка в рекурсивной версии — возвращать площадь как 1 + sink(...) + sink(...) + ... и забыть вернуть 0 для воды и выхода за границы. Python в этом случае вернёт None, и сложение упадёт с TypeError.

Вариация: Surrounded Regions

LeetCode 130: сетка из 'X' и 'O'. Нужно закрасить в 'X' все области из 'O', полностью окружённые 'X'. Область, которая касается края доски, не окружена и остаётся как есть.

Пример:

До:        После:
X X X X    X X X X
X O O X    X X X X
X X O X    X X X X
X O X X    X O X X

Область из трёх 'O' в центре окружена и закрашивается. Одиночная 'O' в нижней строке лежит на краю, поэтому её не трогают.

Прямолинейный подход — для каждой области 'O' запускать обход и проверять, касается ли она края. Работает, но громоздко: сначала нужно обойти область целиком, а уже потом решить, закрашивать ли её, — то есть хранить список клеток или обходить второй раз.

Проще перевернуть задачу: найти не те области, которые надо закрасить, а те, которые закрашивать нельзя. Это ровно те 'O', до которых можно дойти от края. Запускаем обход сразу из всех 'O' на границе (это мультиисточниковый обход) и помечаем достижимые клетки временным символом '#'. Всё, что осталось 'O', окружено.

def solve_surrounded(board):
    rows, cols = len(board), len(board[0])
    stack = []
    for r in range(rows):
        for c in range(cols):
            on_border = r in (0, rows - 1) or c in (0, cols - 1)
            if on_border and board[r][c] == 'O':
                board[r][c] = '#'
                stack.append((r, c))
    while stack:
        cr, cc = stack.pop()
        for dr, dc in DIRS:
            nr, nc = cr + dr, cc + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O':
                board[nr][nc] = '#'
                stack.append((nr, nc))
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == '#':
                board[r][c] = 'O'
    return board

Три фазы: пометить граничные 'O', распространить пометку обходом, затем одним проходом закрасить оставшиеся 'O' и вернуть '#' обратно в 'O'. Время $O(m \cdot n)$. Порядок проверок в последнем цикле важен: если сначала превратить '#' в 'O', а потом все 'O' в 'X', закрасится вся доска.

Тот же приём «обход от границы» решает Pacific Atlantic Water Flow (LeetCode 417): запускаем два обхода — от края каждого океана, двигаясь вверх по высотам, — и берём клетки, достижимые из обоих. И Number of Enclaves (LeetCode 1020): удаляем сушу, связанную с краем, и считаем оставшиеся клетки.

Семейство задач на сетке

После Number of Islands большинство задач на матрицах сводятся к одному из трёх шаблонов:

Отдельно стоит Word Search (её можно решить в нашем тренажёре). Там тоже DFS по сетке с четырьмя направлениями, но цель другая: найти путь, а не компоненту. Поэтому пометку посещения приходится снимать после возврата из рекурсии — это уже бэктрекинг, и каждая клетка может посещаться много раз. Хорошее упражнение — решить обе задачи подряд и сформулировать, почему в Number of Islands клетку можно утопить навсегда, а в Word Search нельзя.

Типичные ошибки

• Пометка после рекурсии или при извлечении. В рекурсивном DFS — бесконечный цикл, в итеративном — дубли в стеке.
• Диагональные соседи. В классической постановке их нет. Если интервьюер говорит «соседи по восьми направлениям», меняется только DIRS.
• Сравнение с числом вместо строки. На LeetCode 200 сетка из строк '1' и '0', а в Max Area of Island — из чисел. Условие grid[r][c] == 1 для строковой сетки всегда ложно, и ответ будет 0.
• Пустая сетка. len(grid[0]) упадёт на []. По ограничениям LeetCode такого входа нет, но проверка в одну строку не помешает.
• list.pop(0) вместо deque в BFS — квадратичное время на больших картах.
• Молчаливая порча входа. Затопление сетки — нормальная оптимизация, но о ней надо сказать. В реальном коде функция, которая «просто считает» и при этом стирает данные вызывающей стороны, — источник неприятных багов.
• Рекурсия без оценки глубины. Не ошибка как таковая, но если не упомянуть риск переполнения стека, интервьюер, скорее всего, спросит о нём сам.

Как это спрашивают на собеседовании

Задача входит практически во все популярные подборки для подготовки (Blind 75, NeetCode 150) и часто служит первым вопросом на графы. Типичный сценарий:

1. Решить базовую задачу любым обходом и назвать сложность.
2. Ответить на вопросы: «Что будет на сетке 10 000 × 10 000?», «Можно ли не менять вход?», «Чем отличаются DFS и BFS здесь?».
3. Follow-up: площадь самого большого острова, подсчёт островов разной формы (Number of Distinct Islands), добавление суши онлайн (Number of Islands II).

Хороший ответ занимает пару минут: «Сетка — это неявный граф, острова — компоненты связности. Иду по клеткам, на каждой непосещённой суше увеличиваю счётчик и обходом помечаю весь остров. $O(mn)$ по времени и памяти. Рекурсия может уйти на глубину $mn$, поэтому пишу через явный стек. Если клетки будут добавляться по одной, переключусь на DSU». В этом ответе есть модель, алгоритм, сложность и ограничения, то есть всё, что хочет услышать интервьюер.