DFS: компоненты связности и заливка

Определение связных компонент

from collections import defaultdict

# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
    graph[u].append(v)
    graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
    if node not in graph:
        graph[node] = []

# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')

Подсчёт связных компонент с помощью DFS

from collections import defaultdict

def count_components(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    count = 0

    def dfs(node):
        visited.add(node)
        for nb in graph[node]:
            if nb not in visited:
                dfs(nb)

    for node in range(n):
        if node not in visited:
            dfs(node)
            count += 1

    return count

print(count_components(6, [(0,1),(0,2),(1,2),(3,4)]))  # 3
print(count_components(5, [(0,1),(1,2),(3,4)]))          # 2

Количество островов

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

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '#'  # mark visited in-place
        dfs(r+1,c); dfs(r-1,c)
        dfs(r,c+1); dfs(r,c-1)

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

grid = [['1','1','0','0','0'],
        ['1','1','0','0','0'],
        ['0','0','1','0','0'],
        ['0','0','0','1','1']]
print(num_islands(grid))  # 3

Алгоритм заливки

def flood_fill(image, sr, sc, new_color):
    original = image[sr][sc]
    if original == new_color:
        return image  # edge case: same color, nothing to do
    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original:
            return
        image[r][c] = new_color
        dfs(r+1,c); dfs(r-1,c)
        dfs(r,c+1); dfs(r,c-1)

    dfs(sr, sc)
    return image

image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]

Максимальная площадь острова

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

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return 0
        if grid[r][c] != 1:
            return 0
        grid[r][c] = 0  # mark visited
        return (1 + dfs(r+1,c) + dfs(r-1,c) +
                dfs(r,c+1) + dfs(r,c-1))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))
    return max_area

grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
        [0,0,0,0,0,0,0,1,1,1,0,0,0],
        [0,1,1,0,1,0,0,0,0,0,0,0,0],
        [0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid))  # 6

Поток воды к Тихому и Атлантическому океанам

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pac = set(); atl = set()

    def dfs(r, c, visited, prev_h):
        if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if heights[r][c] < prev_h:
            return  # water can't flow uphill in reverse
        visited.add((r,c))
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r+dr, c+dc, visited, heights[r][c])

    for r in range(rows):
        dfs(r, 0, pac, heights[r][0])           # Pacific left
        dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
    for c in range(cols):
        dfs(0, c, pac, heights[0][c])            # Pacific top
        dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom

    return sorted(pac & atl)  # intersection

print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))

Итеративный DFS для связных компонент

def count_components_iterative(n, edges):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = set()
    count = 0

    for start in range(n):
        if start in visited:
            continue
        # Iterative DFS
        stack = [start]
        while stack:
            node = stack.pop()
            if node in visited:
                continue
            visited.add(node)
            for nb in graph[node]:
                if nb not in visited:
                    stack.append(nb)
        count += 1

    return count

print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)]))  # 3

Окружённые области

def solve(board):
    if not board:
        return
    rows, cols = len(board), len(board[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != 'O':
            return
        board[r][c] = 'S'  # safe: connected to border
        dfs(r+1,c); dfs(r-1,c)
        dfs(r,c+1); dfs(r,c-1)

    # Mark border-connected O's as safe
    for r in range(rows):
        dfs(r, 0); dfs(r, cols-1)
    for c in range(cols):
        dfs(0, c); dfs(rows-1, c)

    # Flip: surrounded O -> X, safe S -> O
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O': board[r][c] = 'X'
            elif board[r][c] == 'S': board[r][c] = 'O'

board = [['X','X','X','X'],['X','O','O','X'],
         ['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]])  # X, O

Подсчёт подостровов

def count_sub_islands(grid1, grid2):
    rows, cols = len(grid2), len(grid2[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return True
        if grid2[r][c] != 1:
            return True
        grid2[r][c] = 0  # mark visited
        is_sub = grid1[r][c] == 1  # this cell must be in grid1
        is_sub = dfs(r+1,c) and is_sub  # note: AND not short-circuit OR
        is_sub = dfs(r-1,c) and is_sub
        is_sub = dfs(r,c+1) and is_sub
        is_sub = dfs(r,c-1) and is_sub
        return is_sub

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid2[r][c] == 1 and dfs(r, c):
                count += 1
    return count

print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
                         [[1,1,1],[1,0,1],[1,1,1]]))  # 1

DFS и BFS для связных компонент

# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)

# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural

# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')

Острова с ограничениями: формы и периметры

def island_perimeter(grid):
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter += 4  # start with 4 sides
                # Subtract shared edges with adjacent land cells
                if r > 0 and grid[r-1][c] == 1:
                    perimeter -= 2  # shared top edge
                if c > 0 and grid[r][c-1] == 1:
                    perimeter -= 2  # shared left edge
    return perimeter

grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid))  # 16

Быстрая проверка

Повторение урока