← All topics

Graphs

Trees generalized: nodes can have multiple parents, cycles are possible, and the graph might not even be connected. The same DFS/BFS instincts from trees apply, plus a visited set to avoid looping forever.

Easy reps

733. Flood Fill

Given a 2D grid, a starting pixel, and a new color, recolor the starting pixel and every pixel connected to it (up/down/left/right) that shares its original color.

def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image

    def dfs(r, c):
        if (
            0 <= r < len(image)
            and 0 <= c < len(image[0])
            and image[r][c] == old
        ):
            image[r][c] = color
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

    dfs(sr, sc)
    return image

A grid is just a graph where each cell is a node connected to its four neighbors. DFS from the start cell, recoloring as it goes, naturally stops spreading once it hits a cell that's already a different color (the guard clause at the top of dfs).

1791. Find Center of Star Graph

A star graph has one center node connected to every other node. Given its edges, find the center.

def find_center(edges):
    a, b = edges[0]
    c, d = edges[1]
    return a if a in (c, d) else b

The center is the only node that appears in every edge, so it's guaranteed to be shared between the first two edges alone -- no need to scan the whole edge list.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.