Python Algorithms & Data Structures track

Lesson 14 · Part 4: Graph Foundations

DFS

Recursive and stack-based DFS, visited state and connected components

Part 4: Graph Foundations3 min readFree lesson

Part 04 – Graph Basics | Difficulty: ⭐⭐⭐☆☆

Introduction: Depth-First Search

DFS (Depth-First Search) is a method where you explore as deep as possible from the current node first, then return back.

Applications:

Searching for connected components
Cycle detection
Backtracking (complete search)
Topological sorting (DFS-based)
Tree traversal

Learning Goals

Implement recursive DFS and stack DFS and explain the difference in visit order.
Update the visited array at the correct timing to prevent infinite loops.
Solve Island/Area search problems with grid DFS.

Key Concepts

DFS Search Order Diagram

Graph:
  1 ─── 2 ─── 5
  │     │
  3 ─── 4

DFS (start=1) search order:
Visited: 1 → 2 → 5 (blocked, backtrack) → 4 → 3 (blocked, backtrack)
Result: [1, 2, 5, 4, 3]

Stack simulation:
  push(1)
stack=[1]         → pop=1, visit[1], push(3,2)
stack=[3,2]       → pop=2, visit[2], push(5,4)
stack=[3,5,4]     → pop=4, visit[4]
stack=[3,5]       → pop=5, visit[5]
stack=[3]         → pop=3, visit[3]
Result: [1,2,4,5,3]  ← may differ from recursion in order

Recursive DFS vs Stack DFS

Item	Recursive DFS	Stack DFS
Code Simplicity	Simple	Explicit stack needed
Stack Overflow	Risky (depth limit)	None
Visit Order	In the order of adjacency list	Need to push in reverse order
Actual Problems	Mainly use recursion	Used when recursion is not possible

Visited Array Setting Timing

#Correct method: process visit first, then explore
def dfs(node):
    visited[node] = True      #← here
    for nxt in graph[node]:
        if not visited[nxt]:
            dfs(nxt)

#Common mistake in stack DFS:
#marking visited when popping → the same node can be pushed multiple times
#marking visited when pushing → correct

Time/Space Complexity

Time: O(V + E) — visit all nodes and edges once
Space: O(V) — visited array + recursion stack (worst case O(V))

Example

File	Contents
`src/01_recursive_dfs.py`	Recursive DFS template, visit order
`src/02_stack_dfs.py`	Stack-based DFS, comparison with recursion
`src/03_connected_components.py`	Counting the number of connected components
`src/04_dfs_grid.py`	Grid DFS, 4-direction movement

5 Common Mistakes

Mistake of marking visited after recursive call

def dfs(node):
    for nxt in graph[node]:
        if not visited[nxt]:
            dfs(nxt)
    visited[node] = True    #← Wrong! Infinite loop possible

Recursion depth exceeded (RecursionError)

If the graph has a linear (chain) structure, DFS depth = number of nodes
Need to increase it using sys.setrecursionlimit(10**6)
Or switch to stack-based DFS

Error in visit timing in stack DFS

#Wrong method: mark visited after pop
while stack:
    node = stack.pop()
    if visited[node]: continue
    visited[node] = True    #Mark visited after pop (duplicate push occurs)
#Correct method: mark visited when pushing
stack.append(start)
visited[start] = True
while stack:
    node = stack.pop()
    for nxt in graph[node]:
        if not visited[nxt]:
            visited[nxt] = True
            stack.append(nxt)

Missing boundary check in grid search

for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
    nr, nc = r + dr, c + dc
    #Be sure to check the range!
    if 0 <= nr < rows and 0 <= nc < cols:
        ...

Only exploring the starting point in disconnected graph

To cover all nodes, iterate over all nodes and start DFS at unvisited nodes
```
for node in range(1, n + 1):
    if not visited[node]:
        dfs(node)
```

Summary

Purpose	Code pattern
Simple visit order	Recursive DFS
Counting connected components	for loop + DFS
Grid island search	4-direction DFS
Overcoming recursion limit	Stack DFS

Try It Yourself

In a 5×5 grid, use DFS to count the number of islands connected to 1.
Modify stack DFS so that recursive DFS and stack DFS output the same visit order.
Calculate the DFS visit order of the following graph by hand: 1-2, 1-3, 2-4, 3-4, 4-5

Example files

The runnable files used in this lesson. Copy them into your own project and experiment.

src/01_recursive_dfs.pyPython

"""Topic  : Recursive DFS Template — Visit Order, Tree/Graph
Time   : O(V + E)
Space  : O(V) Recursive Stack"""

import sys
sys.setrecursionlimit(100_000)


#── Basic Recursive DFS ─────────────────────────────────────────────────────────────

def dfs(
    graph: list[list[int]],
    node: int,
    visited: list[bool],
    order: list[int],
) -> None:
    """Recursive DFS.

    Args:
        graph: Adjacency list (1-indexed)
        node: Current node
        visited: Whether visited
        order: Records visit order"""
    visited[node] = True
    order.append(node)
    for nxt in graph[node]:
        if not visited[nxt]:
            dfs(graph, nxt, visited, order)


def dfs_with_depth(
    graph: list[list[int]],
    node: int,
    visited: list[bool],
    depth: int = 0,
) -> None:
    """Visualize DFS with indentation."""
    visited[node] = True
    indent = "  " * depth
    print(f"{indent}→ Visit Node {node} (Depth={depth})")
    for nxt in sorted(graph[node]):
        if not visited[nxt]:
            dfs_with_depth(graph, nxt, visited, depth + 1)
    print(f"{indent}← Return to Node {node}")


#── Pre/Post DFS ─────────────────────────────────────────────────────────

def dfs_pre_post(
    graph: list[list[int]],
    node: int,
    visited: list[bool],
    pre: list[int],
    post: list[int],
) -> None:
    """Record pre-order and post-order.

    Reverse of post-order: used in topological sorting."""
    visited[node] = True
    pre.append(node)
    for nxt in graph[node]:
        if not visited[nxt]:
            dfs_pre_post(graph, nxt, visited, pre, post)
    post.append(node)


#── Connectivity Check ────────────────────────────────────────────────────────────

def is_reachable(
    graph: list[list[int]], src: int, dst: int, n: int
) -> bool:
    """Can it reach from src to dst?"""
    visited = [False] * (n + 1)
    order: list[int] = []
    dfs(graph, src, visited, order)
    return visited[dst]


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Graph Construction
    #    1 ─── 2 ─── 5
    #    │     │
    #    3 ─── 4
    n = 5
    edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 4)]
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    print("=" * 50)
    print("Recursive DFS — Visit Order")
    print("=" * 50)
    visited = [False] * (n + 1)
    order: list[int] = []
    dfs(graph, 1, visited, order)
    print(f"DFS Visit Order (Start=1): {order}")

    print("\n=== DFS Depth Visualization ===")
    visited2 = [False] * (n + 1)
    dfs_with_depth(graph, 1, visited2)

    #Preorder/Postorder Sequence
    print("\n=== Preorder / Postorder Sequence ===")
    visited3 = [False] * (n + 1)
    pre: list[int] = []
    post: list[int] = []
    dfs_pre_post(graph, 1, visited3, pre, post)
    print(f"Preorder (pre) Sequence  : {pre}")
    print(f"Postorder (post) Sequence : {post}")
    print(f"Reverse Postorder       : {post[::-1]}  ← Used for Topological Sorting")

    #Reachability
    print("\n=== Reachability ===")
    for src, dst in [(1, 5), (1, 3), (5, 3)]:
        print(f"  {src} → {dst}: {is_reachable(graph, src, dst, n)}")

    #Disconnected Graph
    print("\n=== Disconnected Graph ===")
    #1─2  3─4  5(Isolated)
    n2 = 5
    edges2 = [(1, 2), (3, 4)]
    g2: list[list[int]] = [[] for _ in range(n2 + 1)]
    for u, v in edges2:
        g2[u].append(v)
        g2[v].append(u)

    vis2 = [False] * (n2 + 1)
    components = 0
    for node in range(1, n2 + 1):
        if not vis2[node]:
            ord2: list[int] = []
            dfs(g2, node, vis2, ord2)
            components += 1
            print(f"Connected Component {components}: {ord2}")
    print(f"Total Number of Connected Components: {components}")

src/02_stack_dfs.pyPython

"""Topic  : Stack-based DFS — Comparison with Recursion
Time   : O(V + E)
Space  : O(V)"""


#── Stack DFS ──────────────────────────────────────────────────────────────────

def dfs_stack(
    graph: list[list[int]],
    start: int,
    n: int,
) -> list[int]:
    """Stack-based DFS.

    Mark as visited when pushing → Correct method."""
    visited = [False] * (n + 1)
    stack = [start]
    visited[start] = True
    order: list[int] = []

    while stack:
        node = stack.pop()
        order.append(node)
        #Push in reverse order to match the sequence of recursive DFS
        for nxt in reversed(graph[node]):
            if not visited[nxt]:
                visited[nxt] = True
                stack.append(nxt)

    return order


def dfs_stack_verbose(
    graph: list[list[int]],
    start: int,
    n: int,
) -> list[int]:
    """Step-by-step output of stack DFS."""
    visited = [False] * (n + 1)
    stack = [start]
    visited[start] = True
    order: list[int] = []

    print(f"Initial stack: {stack}")
    step = 0
    while stack:
        node = stack.pop()
        order.append(node)
        step += 1
        neighbors_added = []
        for nxt in reversed(graph[node]):
            if not visited[nxt]:
                visited[nxt] = True
                stack.append(nxt)
                neighbors_added.append(nxt)
        print(f"Step {step:2d}: pop={node}, push={neighbors_added},"
              f"Stack={stack}")

    print(f"Visit order: {order}")
    return order


#── Recursive DFS ─────────────────────────────────────────────────────────────────

def dfs_recursive(
    graph: list[list[int]],
    start: int,
    n: int,
) -> list[int]:
    """Recursive DFS."""
    visited = [False] * (n + 1)
    order: list[int] = []

    def _dfs(node: int) -> None:
        visited[node] = True
        order.append(node)
        for nxt in graph[node]:
            if not visited[nxt]:
                _dfs(nxt)

    _dfs(start)
    return order


#── Demonstration of common mistakes in Stack DFS ─────────────────────────────────

def dfs_stack_wrong(
    graph: list[list[int]],
    start: int,
    n: int,
) -> list[int]:
    """Incorrect stack DFS: mark as visited after popping.

    The same node can enter the stack multiple times."""
    visited = [False] * (n + 1)
    stack = [start]
    order: list[int] = []
    push_count = [0]

    while stack:
        node = stack.pop()
        if visited[node]:
            continue         #Already visited node → duplicate handling
        visited[node] = True
        order.append(node)
        for nxt in graph[node]:
            if not visited[nxt]:
                stack.append(nxt)
                push_count[0] += 1

    print(f"(Incorrect method) Number of pushes: {push_count[0]}")
    return order


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Graph Construction
    n = 6
    edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
    graph: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    print("=" * 55)
    print("Stack DFS vs Recursive DFS comparison")
    print("=" * 55)

    stack_order = dfs_stack(graph, 1, n)
    rec_order = dfs_recursive(graph, 1, n)

    print(f"Recursive DFS order: {rec_order}")
    print(f"Stack DFS order: {stack_order}")
    print(f"Does the order match: {rec_order == stack_order}")

    print("\n=== Step-by-step visualization of Stack DFS ===")
    dfs_stack_verbose(graph, 1, n)

    print("\n=== Incorrect method vs Correct method ===")
    print("Incorrect method (mark visited after pop):")
    wrong_order = dfs_stack_wrong(graph, 1, n)
    print(f"Visit order: {wrong_order}")

    print("Correct method (mark visited when pushing):")
    correct_order = dfs_stack(graph, 1, n)
    push_estimate = sum(len(graph[i]) for i in range(1, n + 1))
    print(f"Visit order: {correct_order}")
    print(f"Number of pushes: {n - 1} times (number of nodes - 1)")

    #Use in environments without recursion
    print("=== Overcoming recursion limit ===")
    print("Python default recursion limit: 1,000")
    print("For large graphs, stack DFS is required")
    print("Or set sys.setrecursionlimit(10**6)")

src/03_connected_components.pyPython

"""Topic  : Connected Components — Counting and Classification with DFS
Time   : O(V + E)
Space  : O(V)"""

import sys
sys.setrecursionlimit(100_000)


#── Number of Connected Components ───────────────────────────────────────────────

def count_components(n: int, graph: list[list[int]]) -> int:
    """Returns the number of connected components in an undirected graph."""
    visited = [False] * (n + 1)
    count = 0

    def dfs(node: int) -> None:
        visited[node] = True
        for nxt in graph[node]:
            if not visited[nxt]:
                dfs(nxt)

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

    return count


#── Classification of Connected Components ───────────────────────────────────────

def find_components(
    n: int, graph: list[list[int]]
) -> list[list[int]]:
    """Returns the list of nodes belonging to each connected component."""
    visited = [False] * (n + 1)
    components: list[list[int]] = []

    def dfs(node: int, component: list[int]) -> None:
        visited[node] = True
        component.append(node)
        for nxt in graph[node]:
            if not visited[nxt]:
                dfs(nxt, component)

    for node in range(1, n + 1):
        if not visited[node]:
            comp: list[int] = []
            dfs(node, comp)
            components.append(sorted(comp))

    return components


#── Label Array ────────────────────────────────────────────────────────────────

def label_components(
    n: int, graph: list[list[int]]
) -> list[int]:
    """Returns the connected component number that each node belongs to (1-indexed).

    Nodes in the same connected component have the same number."""
    label = [0] * (n + 1)   #0 = Unvisited
    comp_id = 0

    def dfs(node: int, cid: int) -> None:
        label[node] = cid
        for nxt in graph[node]:
            if label[nxt] == 0:
                dfs(nxt, cid)

    for node in range(1, n + 1):
        if label[node] == 0:
            comp_id += 1
            dfs(node, comp_id)

    return label


#── Main ─────────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Graph 1: 3 Connected Components
    #  1─2   3─4─5   6
    n1 = 6
    edges1 = [(1, 2), (3, 4), (4, 5)]
    g1: list[list[int]] = [[] for _ in range(n1 + 1)]
    for u, v in edges1:
        g1[u].append(v)
        g1[v].append(u)

    print("=" * 50)
    print("Connected Component Search")
    print("=" * 50)
    print(f"Graph 1: 1─2   3─4─5   6")
    cnt = count_components(n1, g1)
    comps = find_components(n1, g1)
    labels = label_components(n1, g1)

    print(f"Number of Connected Components: {cnt}")
    for i, comp in enumerate(comps, 1):
        print(f"Component {i}: {comp}")
    print(f"Label Array: {labels[1:]}")

    #Graph 2: Fully Connected
    #  1─2─3─4─5
    n2 = 5
    edges2 = [(1, 2), (2, 3), (3, 4), (4, 5)]
    g2: list[list[int]] = [[] for _ in range(n2 + 1)]
    for u, v in edges2:
        g2[u].append(v)
        g2[v].append(u)

    print(f"\nGraph 2: 1─2─3─4─5 (Linear)")
    cnt2 = count_components(n2, g2)
    comps2 = find_components(n2, g2)
    print(f"Number of Connected Components: {cnt2}")
    print(f"Connected Components: {comps2}")

    #Graph 3: All Isolated
    n3 = 4
    g3: list[list[int]] = [[] for _ in range(n3 + 1)]
    print(f"\nGraph 3: 1  2  3  4 (All Isolated)")
    cnt3 = count_components(n3, g3)
    print(f"Number of Connected Components: {cnt3}")

    #Application: Node Coloring (Bipartite Graph Check)
    print("\n=== Bipartite Graph Check ===")
    def is_bipartite(n: int, graph: list[list[int]]) -> bool:
        color = [-1] * (n + 1)

        def dfs_color(node: int, c: int) -> bool:
            color[node] = c
            for nxt in graph[node]:
                if color[nxt] == -1:
                    if not dfs_color(nxt, 1 - c):
                        return False
                elif color[nxt] == c:
                    return False
            return True

        for node in range(1, n + 1):
            if color[node] == -1:
                if not dfs_color(node, 0):
                    return False
        return True

    #Bipartite Graph
    g_bip: list[list[int]] = [[] for _ in range(5)]
    for u, v in [(1, 2), (1, 4), (3, 2), (3, 4)]:
        g_bip[u].append(v)
        g_bip[v].append(u)
    print(f"Bipartite Graph (Square): {is_bipartite(4, g_bip)}")

    #Odd Cycle
    g_odd: list[list[int]] = [[] for _ in range(4)]
    for u, v in [(1, 2), (2, 3), (3, 1)]:
        g_odd[u].append(v)
        g_odd[v].append(u)
    print(f"Odd Cycle (Triangle): {is_bipartite(3, g_odd)}")

src/04_dfs_grid.pyPython

"""Topic  : Grid DFS — Island (Area) Exploration, 4-Directional Movement
Time   : O(R × C)
Space  : O(R × C) Recursive Stack"""

import sys
sys.setrecursionlimit(200_000)

#4 directions: up, down, left, right
DR4 = [-1, 1, 0, 0]
DC4 = [0, 0, -1, 1]

#8 directions: including diagonals
DR8 = [-1, -1, -1, 0, 0, 1, 1, 1]
DC8 = [-1, 0, 1, -1, 1, -1, 0, 1]


#── Counting the number of islands ────────────────────────────────────────────────────────────

def count_islands(grid: list[list[str]]) -> int:
    """Return the number of islands marked with '1' (4-directional connectivity).

    Visit islands with DFS and mark them as '0'."""
    rows = len(grid)
    cols = len(grid[0])

    def dfs(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'       #Mark as visited
        for i in range(4):
            dfs(r + DR4[i], c + DC4[i])

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


#── List of island sizes ────────────────────────────────────────────────────────────

def island_sizes(grid: list[list[int]]) -> list[int]:
    """Return a list of the sizes (number of cells) of each island.

    grid: 0=sea, 1=land"""
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    sizes: list[int] = []

    def dfs(r: int, c: int) -> int:
        visited[r][c] = True
        size = 1
        for i in range(4):
            nr, nc = r + DR4[i], c + DC4[i]
            if (0 <= nr < rows and 0 <= nc < cols
                    and not visited[nr][nc] and grid[nr][nc] == 1):
                size += dfs(nr, nc)
        return size

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                sizes.append(dfs(r, c))

    return sorted(sizes)


#── Numbering complexes (Baekjoon 2667 style) ──────────────────────────────────────

def label_and_count(grid: list[list[int]]) -> tuple[int, list[int]]:
    """Number each complex and return (number of complexes, list of sizes of each complex).

    Baekjoon 2667 style."""
    rows = len(grid)
    cols = len(grid[0])
    label = [[0] * cols for _ in range(rows)]
    comp_id = 0
    sizes: list[int] = []

    def dfs(r: int, c: int, cid: int) -> int:
        label[r][c] = cid
        size = 1
        for i in range(4):
            nr, nc = r + DR4[i], c + DC4[i]
            if (0 <= nr < rows and 0 <= nc < cols
                    and label[nr][nc] == 0 and grid[nr][nc] == 1):
                size += dfs(nr, nc, cid)
        return size

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and label[r][c] == 0:
                comp_id += 1
                sizes.append(dfs(r, c, comp_id))

    return comp_id, sorted(sizes)


#── Output ───────────────────────────────────────────────────────────────────

def print_grid(grid: list[list], title: str = "Grid") -> None:
    """Print the grid."""
    print(f"\n=== {title} ===")
    for row in grid:
        print("  " + "".join(str(c) for c in row))


#── Main ─────────────────────────────────────────────────────────────────────

if __name__ == "__main__":
    #Counting the number of islands
    grid1 = [
        list("11010"),
        list("11010"),
        list("00100"),
        list("10001"),
    ]
    print_grid(grid1, "Original grid (1=land, 0=sea)")
    cnt = count_islands([row[:] for row in grid1])  #Pass a copy
    print(f"Number of islands: {cnt}")

    #Island size
    grid2 = [
        [1, 1, 0, 1, 0],
        [1, 1, 0, 1, 0],
        [0, 0, 1, 0, 0],
        [1, 0, 0, 0, 1],
    ]
    print_grid(grid2, "Island size grid")
    sizes = island_sizes(grid2)
    print(f"List of island sizes (ascending order): {sizes}")
    print(f"Total number of islands: {len(sizes)}, largest island: {max(sizes)}")

    #Numbering complexes (Baekjoon 2667 style)
    grid3 = [
        [0, 1, 1, 0, 1, 0, 0],
        [0, 1, 1, 0, 1, 0, 1],
        [1, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 1],
        [0, 1, 0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0, 0, 0],
    ]
    print_grid(grid3, "Complex grid (Baekjoon 2667 style)")
    num_comps, comp_sizes = label_and_count(grid3)
    print(f"Number of complexes: {num_comps}")
    print(f"Number of houses per complex (ascending order): {comp_sizes}")

    #Verify accuracy
    assert count_islands([list("11010"),
                           list("11010"),
                           list("00100"),
                           list("10001")]) == 3
    print("Accuracy check: PASS")

Assignment

Solve connected components and grid search problems using DFS.

Problem List

#	Problem	Tier	Key Skill
1	Baekjoon 2606 – Virus	Silver III	Size of connected components
2	Baekjoon 2667 – Numbering Complexes	Silver I	Grid DFS + Size
3	Baekjoon 1012 – Organic Cabbage	Silver II	Grid DFS

Problem 1: Baekjoon 2606 – Virus (Silver III)

Problem Description

Find the number of computers infected starting from computer 1.

Approach

DFS search starting from computer 1
Number of visited nodes - 1 (excluding computer 1)

Problem 2: Baekjoon 2667 – Numbering Complexes (Silver I)

Problem Description

Group connected houses into complexes in an NxN grid, and print the number of complexes and the size of each complex in ascending order.

Input format

Approach

for r in range(n):
    for c in range(n):
        if grid[r][c] == 1 and not visited[r][c]:
            size = dfs(r, c)
            sizes.append(size)

Notes

Input is a string → conversion to int needed
Boundary check required

Problem 3: Baekjoon 1012 – Organic Cabbage (Silver II)

Problem Description

Find the number of connected cabbage components in an MxN grid. (One worm handles one connected component)

Approach

Same as problem 2667 but:

Multiple test cases
M×N grid (M≠N possible)
Cabbage coordinates given as (x, y) → careful conversion to (row, column)

Pre-submission Checklist

2606: Are you counting the number of visits excluding the start node (1)?
2667: Did you convert the grid input to int?
2667: Did you sort in ascending order before printing?
1012: Is the conversion of cabbage coordinates (x, y) → (row=y, column=x) correct?
1012: Did you initialize the graph for each test case?
All: Did you set the recursion limit with sys.setrecursionlimit?

Model Answer

Refer to the reference solution below.

Show the reference solution

Try the assignment yourself first — comparing your attempt with a working solution is where most of the learning happens.

boj_1012.pyPython

"""Baekjoon 1012 – Organic Cabbage
https://www.acmicpc.net/problem/1012
Time  : O(M × N)
Space : O(M × N)"""

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]


def main() -> None:
    t = int(input())
    for _ in range(t):
        m, n, k = map(int, input().split())
        grid = [[0] * m for _ in range(n)]

        for _ in range(k):
            x, y = map(int, input().split())
            grid[y][x] = 1    #Note: x = column, y = row

        visited = [[False] * m for _ in range(n)]

        def dfs(r: int, c: int) -> None:
            visited[r][c] = True
            for i in range(4):
                nr, nc = r + DR[i], c + DC[i]
                if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and grid[nr][nc] == 1:
                    dfs(nr, nc)

        count = 0
        for r in range(n):
            for c in range(m):
                if grid[r][c] == 1 and not visited[r][c]:
                    dfs(r, c)
                    count += 1

        print(count)


if __name__ == "__main__":
    main()

boj_2606.pyPython

"""Baekjoon 2606 – Virus
https://www.acmicpc.net/problem/2606
Time  : O(V + E)
Space : O(V + E)"""

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def main() -> None:
    n = int(input())
    m = int(input())
    graph: list[list[int]] = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    visited = [False] * (n + 1)
    count = [0]

    def dfs(node: int) -> None:
        visited[node] = True
        for nxt in graph[node]:
            if not visited[nxt]:
                count[0] += 1
                dfs(nxt)

    dfs(1)
    print(count[0])


if __name__ == "__main__":
    main()

boj_2667.pyPython

"""Baekjoon 2667 – Numbering Complexes
https://www.acmicpc.net/problem/2667
Time  : O(N²)
Space : O(N²)"""

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

DR = [-1, 1, 0, 0]
DC = [0, 0, -1, 1]


def main() -> None:
    n = int(input())
    grid = [list(map(int, list(input().rstrip()))) for _ in range(n)]
    visited = [[False] * n for _ in range(n)]
    sizes: list[int] = []

    def dfs(r: int, c: int) -> int:
        visited[r][c] = True
        size = 1
        for i in range(4):
            nr, nc = r + DR[i], c + DC[i]
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
                size += dfs(nr, nc)
        return size

    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1 and not visited[r][c]:
                sizes.append(dfs(r, c))

    sizes.sort()
    print(len(sizes))
    print('\n'.join(map(str, sizes)))


if __name__ == "__main__":
    main()

Learn this lesson with a mentor

Work through the Python Algorithms & Data Structures track on your own, or join a guided cohort at our Pitampura campus and online.

Enroll now Track overview