Graph Algorithms & Search

Most graph problems never say "graph"

A lock has four wheels, each showing a digit from 0 to 9. It starts at 0000. One move turns one wheel one notch up or down, and 9 wraps around to 0. A few combinations are dead ends: land on one and the lock jams. What is the fewest number of moves to reach 0202? This is LeetCode 752: Open the Lock.

The obvious plan tries move sequences, shortest first. Every position offers 8 moves (4 wheels × 2 directions), so there are 8ᵈ sequences of length d. The farthest combination, 5555, is 20 moves from 0000. Trying every sequence up to length 20 means about 1.3 × 10¹⁸ sequences. At a billion per second, that takes over 40 years.

But the lock has only 10,000 positions. Almost every one of those sequences revisits a position that another sequence already reached. Up on wheel 1, then down on wheel 1 comes straight back to 0000. Wheel 1 then wheel 2 lands exactly where wheel 2 then wheel 1 does. The slow plan keeps asking "how far away is this position?" about positions it has already answered. Treat each position as a node and each move as an edge, expand each node once, and the whole search costs at most 10,000 × 8 = 80,000 neighbor checks.

That is the lesson in two sentences. Decide what a node is and what an edge is. Then read the question again, because the question picks the algorithm. The cost depends on how many nodes and edges your model has, not on how many paths exist.

You should be comfortable with Python sets, dictionaries and tuples as keys (Hash Maps & Sets), and with recursion and the call stack (Advanced Recursion & Backtracking). This lesson is the map: modelling, storage, choosing the algorithm, and union-find in full. Graph Traversal takes DFS and BFS apart in depth, and Shortest Path Algorithms covers Dijkstra and its relatives.

Step 1: Model it — what is a node, what is an edge?

Smell: the statement talks about things and the moves or relationships between them. Cells you can walk between, words one letter apart, courses that unlock other courses, cables between computers.

Three shapes of graph

• Explicit. You are handed n and a list of pairs, such as edges = [[0, 1], [1, 2]]. Course Schedule and Redundant Connection look like this.
• Grid. Each cell is a node, and edges join neighboring cells, usually in 4 directions and only through open cells. Number of Islands and Rotting Oranges look like this.
• Implicit, or state graph. Nodes are configurations you generate on the fly, and edges are legal moves. You never store the whole graph. Open the Lock, Word Ladder and sliding-tile puzzles look like this.

A little vocabulary, used throughout:

The lock has 10,000 × 8 / 2 = 40,000 edges, because each undirected edge touches two positions. A simple undirected graph has at most V(V − 1)/2 edges. Graphs with E close to V are sparse; graphs with E close to V² are dense. Most LeetCode graph inputs are sparse, with E a small multiple of V.

Translate before you code

Before touching the keyboard, fill in one row of this table:

If you cannot fill in a column, you are not ready to pick an algorithm yet.

Arrows have a direction, and you choose it

In LeetCode 210: Course Schedule II, prerequisites[i] = [a, b] means "take b before a". Draw the edge b → a, read as "b unlocks a". A valid plan then lists every edge's tail before its head.

You could draw a → b ("a needs b") instead. That graph is just as correct, but the same algorithm then produces the plan backwards, with dependents first. Neither direction is wrong. Mixing them is. Pick one, write it in a comment, and build every edge the same way.

Predict first: with prerequisites = [[1, 0], [2, 1]] and edges drawn b → a, which course has no incoming edge, and what does that tell you?

A node is everything the future depends on

Smell: the same place can be good or bad depending on something you carry, such as keys collected, walls you may still break, or the direction you face.

Take LeetCode 1293: Shortest Path in a Grid with Obstacles Elimination. Walk from the top-left to the bottom-right of a grid of 0 (open) and 1 (wall). You may break at most k walls. What is the fewest number of steps? The tempting node is the cell (r, c). But two arrivals at the same cell are not interchangeable: one that can still break a wall may smash through later, and one that cannot is stuck.

Here is a 4 × 2 grid with k = 1:

      col 0  col 1
row 0   S      .
row 1   #      .
row 2   #      #
row 3   #      T

The only route that works breaks the wall at (2, 1): S → (0, 1) → (1, 1) → (2, 1) → T, 4 steps. But (1, 1) can also be reached in 2 steps by breaking (1, 0). A search that looks at "down" before "right" gets there that way first, with no breaks left. If its seen set holds bare cells, it marks (1, 1) as done. The later arrival through (0, 1), which still has its break, is thrown away, and the search reports −1. The fix is to make the node (row, col, breaks left). That multiplies the node count by (k + 1), and it is exactly the information the future needs. Challenge 3 of the final round solves it in full.

The rule cuts both ways. Put everything that affects future moves into the node, and nothing else. In particular, don't put the step count in the node. Two arrivals at the same place after the same number of steps would still merge, but arrivals after different numbers of steps would not, so every position gets re-explored once per distance. On the lock, the first 20 moves produce 57,500 (position, steps) pairs where plain positions number 10,000, and the count keeps growing: if the target is unreachable, the search never ends.

Your turn: model it. LeetCode 433: Minimum Genetic Mutation gives gene strings of 8 characters from A, C, G, T. One mutation changes one character, and every gene you pass through, including the end, must be in bank (at most 10 strings). Find the fewest mutations from start to end, or −1. Before writing code: what is a node, what is an edge, how many candidate neighbors does one gene have, how many nodes can the search ever visit, and which tool fits?

from collections import deque

def min_mutation(start, end, bank):
    allowed = set(bank)
    if end not in allowed:
        return -1
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        gene, steps = queue.popleft()
        if gene == end:
            return steps
        for i in range(len(gene)):
            for ch in "ACGT":
                nxt = gene[:i] + ch + gene[i + 1:]
                if nxt in allowed and nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, steps + 1))
    return -1

print(min_mutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]))   # 2

Step 2: Store it — representations and what they cost

Smell: the input is a list of pairs, but your search keeps asking "who are the neighbors of u?"

Four ways to hold a graph

• Edge list: [(u, v), ...], the way input usually arrives. Finding u's neighbors means scanning every edge.
• Adjacency list: graph[u] is a list of u's neighbors. This is the default for searching.
• Adjacency matrix: M[u][v] is 1 (or a weight) when the edge exists. You get an O(1) edge check at the price of V² cells.
• Neighbor function: a function that generates u's neighbors when asked, as in the lock. Nothing is stored.

Put numbers on it. With V = 100,000 and E = 200,000, a matrix needs 10¹⁰ cells, which is 10 GB even at one byte per cell. The adjacency list holds 400,000 neighbor entries (each undirected edge is stored twice, once at each end) in 100,000 lists.

A matrix is fine when V is small (1,000 nodes is 10⁶ cells) or the graph is dense. Sometimes the input already is a matrix. Then scanning a node's row costs V no matter how few neighbors it has, so any traversal costs Θ(V²).

Building the list, and two Python traps

def build_graph(n, edges, directed=False):
    graph = [[] for _ in range(n)]      # one fresh list per node
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

print(build_graph(4, [[0, 1], [0, 2], [1, 2]]))   # [[1, 2], [0, 2], [0, 1], []]

Node 3 has no edges, and it still gets an empty list. That matters.

Predict first: what does this print?

graph = [[]] * 3
graph[0].append(1)
print(graph)

⚠️ Isolated nodes vanish from edge-built dictionaries. If you build graph = defaultdict(list) from the edges alone, a node with no edges never becomes a key, and for u in graph skips it. A component count then comes out one short per isolated node. When nodes are 0..n-1, build from range(n) as above. When labels are words or coordinates, a defaultdict is right, but keep the full node list separately.

Grids: the graph you never build

A grid is already an adjacency structure. Generate neighbors with direction vectors:

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]    # down, up, right, left

def grid_neighbors(grid, r, c):
    rows, cols = len(grid), len(grid[0])
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:   # both bounds, before indexing
            yield nr, nc

⚠️ Negative indexes don't crash in Python. Check only nr < rows and nr = -1 slips through: grid[-1] quietly reads the last row. There is no IndexError, just a wrong answer, and it shows up only when an edge cell's wrap-around partner happens to be open. Check both bounds, every time.

Size a grid before you search it. An R × C grid has V = R·C nodes. With 4-directional moves it has R(C − 1) horizontal and (R − 1)C vertical edges, fewer than 2RC in total. A 300 × 300 grid is 90,000 nodes and 179,400 edges, so any O(V + E) search is O(R·C).

Your turn: a 3 × 4 grid with every cell open. How many nodes, edges and adjacency-list entries? How many cells have 2, 3 and 4 neighbors?

Step 3: Search it — one loop, and the container decides

Smell: "can I reach…", "how many groups…", "what is the fewest…".

Reachability: any container works

Every graph search is the same loop. A seen set remembers who has been discovered, and a frontier holds discovered nodes whose neighbors haven't been looked at yet.

def reachable(graph, start):
    seen = {start}
    frontier = [start]
    while frontier:
        node = frontier.pop()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)             # mark when discovered
                frontier.append(nxt)
    return seen

Invariant: everything in seen is reachable from start, and each node enters the frontier at most once. So the loop pops at most V nodes and reads each adjacency list once: O(V + E) time, O(V) extra space. In an undirected graph each edge is read twice, once from each end, which is still O(E).

For reachability the container doesn't matter. Pop from the end (a stack) or from the front (a queue), and you get the same set of nodes in a different order. DFS dives deep first and is most naturally written with recursion. The stack loop above dives too, although its visiting order can differ from a true DFS; that matters only when the order itself is the answer. BFS takes the oldest discovery first.

Counting groups means restarting the loop from every node that no earlier search reached:

def count_components(n, edges):
    graph = build_graph(n, edges)
    seen = [False] * n
    count = 0
    for s in range(n):
        if seen[s]:
            continue
        count += 1                        # s starts a component nobody reached yet
        seen[s] = True
        stack = [s]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
    return count

print(count_components(5, [[0, 1], [1, 2], [3, 4]]))   # 2
print(count_components(6, [[0, 1], [1, 2], [3, 4]]))   # 3: node 5 is alone

Every node is pushed once over all the restarts, so the total is still O(V + E).

Fewest moves: the queue earns its keep

Now the question is "how many edges from the start?" Here the container matters.

from collections import deque

def bfs_distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()            # oldest discovery first
        for nxt in graph[node]:
            if nxt not in dist:           # dist doubles as the seen set
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

Run it from 0 on this six-node ring, built with build_graph(6, [[0, 1], [1, 2], [0, 3], [3, 4], [4, 5], [2, 5]]):

0 --- 1 --- 2
|           |
3 --- 4 --- 5

The result is {0: 0, 1: 1, 3: 1, 2: 2, 4: 2, 5: 3}.

Predict first: change queue.popleft() to queue.pop(), so the deque behaves as a stack. Which distance comes out wrong?

Why the queue gives fewest edges. Invariant: the distances in the queue never decrease from front to back, and they span at most two values, d and d + 1. Nodes therefore leave the queue in order of distance. Suppose w's true distance is d + 1. Then w has a neighbor at distance d, and that neighbor leaves the queue before any node at distance d + 1 or more. So the first node to discover w is at distance d, and w gets label d + 1. The first label is final.

That argument needs every edge to count the same. With costs on the edges, "fewest edges" and "cheapest" are different questions (Step 4).

Mark on discovery. Both functions mark a node when it is added, not when it is popped. Mark at pop time instead, and a node can sit in the queue once per incoming edge. If you also skip already-marked nodes as they are popped, the answers stay right, but the queue grows from O(V) to O(E) entries. Graph Traversal covers when to mark, and why DFS order is different, in depth.

Depth, not size, breaks recursion. A recursive DFS uses one Python frame per level of depth, and the default limit is 1,000 frames (sys.getrecursionlimit()). A 100,000-node star is only two levels deep and runs fine. A path of 1,000 nodes already raises RecursionError. Grids get deep fast: a recursive flood fill on an all-land 300 × 300 grid goes 90,000 calls deep. sys.setrecursionlimit raises the ceiling, but the Python docs warn that a limit set too high can crash the interpreter. An explicit stack, as above, or a queue avoids the question.

⚠️ Marking a grid in place (overwriting visited land '1' with '0') replaces the seen set. It also changes the caller's grid, so check the output contract. And it does not make the search O(1) space: the frontier can still hold a large share of the cells. An explicit-stack flood fill on an all-land 300 × 300 grid peaks at 44,851 stack entries, about half the grid.

Back to the lock

Here is the hook problem, with a neighbor function instead of a stored graph:

from collections import deque

def open_lock(deadends, target):
    seen = set(deadends)                  # dead ends act as already seen: never entered
    if "0000" in seen:
        return -1
    seen.add("0000")
    queue = deque([("0000", 0)])
    while queue:
        state, moves = queue.popleft()
        if state == target:
            return moves
        for i in range(4):
            digit = int(state[i])
            for step in (1, -1):
                nxt = state[:i] + str((digit + step) % 10) + state[i + 1:]
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, moves + 1))
    return -1

print(open_lock(["0201", "0101", "0102", "1212", "2002"], "0202"))   # 6

Without dead ends 0202 is 4 moves away; the dead ends force a detour of 6. Three details decide whether it passes:

• Dead ends are pre-marked as seen, so the search never enters one. LeetCode promises the target is not a dead end. Drop that promise and this version still answers −1 for a dead target, while a version that compares nxt == target before checking the dead ends returns a number for a lock that can never open.
• The target test happens at pop time, so target == "0000" returns 0 without a special case.
• (digit + step) % 10 wraps 9 → 0 and 0 → 9. Python's % never returns a negative for a positive modulus, so −1 becomes 9.

Cost: at most 10,000 states, each generating 8 neighbors, and each neighbor is a 4-character string built in O(4). That is about 320,000 character copies, with expected O(1) set lookups.

💡 Two searches that meet in the middle. When both ends are known, you can run BFS from the start and from the target, expanding the smaller frontier each round, and stop when they touch. With b moves per state and the goal d moves away, one search can touch on the order of b**d states, and two half-depth searches about 2 * b**(d/2). For b = 10 and d = 6, that is 1,000,000 against 2,000. The backward search must follow edges backwards. Lock turns and one-letter word changes are reversible, so the same neighbor function works. For one-way edges, build the reversed edges first. On the lock itself the gain is small, since only 10,000 states exist anyway.

Many starts, one queue

Smell: "the distance to the nearest X" for every cell, or something spreading from many places at once.

LeetCode 542: 01 Matrix asks, for every cell, the number of steps to the nearest 0. Running one BFS per 0 works, but with 1,000 zeros on a 100 × 100 grid that is 1,000 × 10,000 = 10⁷ cell visits, against 10⁴ for a single pass. Instead, put every source in the queue at distance 0 before the loop starts:

from collections import deque

def nearest_zero(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0            # every source starts at distance 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for nr, nc in grid_neighbors(mat, r, c):   # from Step 2
            if dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

print(nearest_zero([[0, 0, 0], [0, 1, 0], [1, 1, 1]]))   # [[0, 0, 0], [0, 1, 0], [1, 2, 1]]

Why it works: picture one invisible super-source joined to every 0 by an edge. A BFS from it reaches all the zeros at distance 1 and everything else one step later than its true distance. Starting with all zeros at distance 0 is that same BFS with the invisible first step removed. The queue starts sorted (all zeros), so the invariant from the last section holds. One pass, O(R·C).

Your turn: predict nearest_zero([[1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 0]]). Then say what a single-source BFS from the bottom-left 0 would get wrong.

[[2, 3, 3, 2],
 [1, 2, 2, 1],
 [0, 1, 1, 0]]

Step 4: Let the question pick the algorithm

You have nodes, edges and a representation. Now read the question once more.

When moves have prices

BFS minimizes the number of edges. When edges carry costs, that is no longer the question:

A --1-- B --1-- C
 \_______5_____/

BFS labels C with distance 1, via the direct edge, which costs 5. The cheapest route is A → B → C, costing 2. Pick the tool by the kind of costs:

0-1 BFS keeps the queue invariant from Step 3. A 0-cost neighbor has the same distance as the node being expanded, so it goes to the front, and the deque stays sorted. One rule from Step 3 does not carry over: don't mark on discovery. A node first reached through a 1-cost edge may later be reached through a 0-cost edge, so lower its distance (and push it again) whenever you find a cheaper route. A node's distance is final when it is popped.

Dijkstra rests on one promise: when a node leaves the heap, its distance is final. That is true when costs are ≥ 0, because every later route only adds cost. A negative edge breaks the promise. With A → B cost 2, A → C cost 3 and C → B cost −2, B leaves the heap at 2. The route A → C → B costs 1, but it only appears after C is popped, too late for an implementation that treats popped nodes as final. Shortest Path Algorithms builds all of these properly; Heaps & Priority Queues explains the heap.

Predict first: a delivery app stores roads with travel times in minutes, all positive. It wants the fewest minutes from the depot to every address. A teammate proposes BFS "because it's a shortest-path problem". What do you say?

"In what order?" — topological sort

Smell: prerequisites, build steps, "X must happen before Y".

A topological order lists the nodes so that every edge points forward. It exists exactly when the directed graph has no cycle: on a cycle, every node waits for the one before it, forever. Kahn's algorithm builds the order greedily. Repeatedly take a node with in-degree 0 (nothing left must come before it), output it, and delete its outgoing edges.

from collections import deque

def course_order(n, prerequisites):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for course, before in prerequisites:  # [a, b] means: take b before a
        graph[before].append(course)      # edge b -> a
        indegree[course] += 1
    ready = deque(c for c in range(n) if indegree[c] == 0)
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for nxt in graph[c]:
            indegree[nxt] -= 1            # one prerequisite of nxt is done
            if indegree[nxt] == 0:
                ready.append(nxt)
    return order if len(order) == n else []   # short output: a cycle blocked the rest

Trace course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]). The edges are 0 → 1, 0 → 2, 1 → 3 and 2 → 3:

    0
   / \
  v   v
  1   2
   \ /
    v
    3

Course 3 waits until both 1 and 2 are done: its in-degree drops to 1, then to 0. Swap the pairs by mistake, building a → b, and the same code returns [3, 1, 2, 0]: the plan backwards.

Why it works. A node enters ready only when every one of its prerequisites is already in order, so every edge points forward. If a cycle exists, no node on it ever reaches in-degree 0, and neither does anything downstream of it. The output comes up short, and the function returns []. That also answers LeetCode 207: Course Schedule ("can you finish?"): return len(order) == n. Cost: O(V + E) time, O(V + E) space.

💡 The order is also a schedule for computing. When a node comes out of ready, every predecessor has already come out. So Kahn's order is the right order to fill in any value that depends on all of a node's predecessors, such as the longest chain of prerequisites leading to each course. That is dynamic programming on a DAG, and it costs nothing beyond the sort itself.

⚠️ Seen twice is not a cycle. In the diagram above, node 3 is reached from 1 and from 2, and there is no cycle. A directed cycle check that says "already seen, so cycle!" reports a false cycle on this diamond. Kahn's algorithm counts in-degrees instead. The DFS version tracks which nodes are on the current path, which Graph Traversal builds step by step.

Your turn: predict course_order(4, [[1, 0], [2, 1], [3, 2], [1, 3]]). Which courses get taken, and which are blocked?

"Every path" is a different question

"List every route" or "every arrangement" asks for output that can be exponential in size. That calls for backtracking DFS (Advanced Recursion & Backtracking): unmark a node on the way back so other paths may use it. A seen set that never forgets would find each node once, which is right for reachability and wrong here.

The map

Step 5: Union-find — groups that keep merging

Smell: edges arrive one at a time, and in between you're asked "are these two connected now?" Or: "which edge is the first to join two things that were already joined?"

The slow way: search again after every cable

A network has 100,000 computers. Then 100,000 cables are plugged in one at a time, and after each one someone asks whether two given machines can talk. Re-running a traversal per question costs up to O(V + E) = 200,000 steps, and 100,000 questions make that 2 × 10¹⁰. The graph only ever grows, yet every search starts from nothing and rediscovers groups it has already found.

Parent pointers and roots

Keep one representative (a root) per group. Every node stores a parent, and following parents always ends at its group's root. Two nodes are connected exactly when they reach the same root. A new edge merges two groups by pointing one root at the other.

n = 6
parent = list(range(n))                   # everyone starts as their own root

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

def union(a, b):
    parent[find(a)] = find(b)             # root of a's group now hangs under b's root

Link the roots, not the nodes. parent[a] = b would tear a, and whatever hangs below it, away from the rest of its old group.

Plot twist: the forest grows a beanstalk

Call union(0, i) for i = 1, 2, …, n − 1. Each call hangs the old root under the new node, so the tree becomes a single chain, and every find(0) walks the whole chain. That adds up to exactly (n − 1)(n − 2)/2 parent hops. For n = 100,000 that is 4,999,850,001, five billion hops to process a hundred thousand edges. The slow search is back, hiding inside find.

Two fixes: union by size and path halving

• Union by size: always hang the smaller tree under the larger root. A node gets one level deeper only when its tree is merged into one at least as large, so the size of its tree at least doubles. That can happen at most log₂ n times, so no node is ever deeper than log₂ n: 16 for n = 100,000.
• Path halving: while walking up in find, point each visited node at its grandparent. Every walk makes the next one shorter.

With both, a long sequence of operations costs O(α(n)) amortized per operation. α is the inverse Ackermann function, which is at most 4 for any input that fits in memory. That is "about constant" with a proof behind it.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))      # every node starts as its own root
        self.size = [1] * n
        self.groups = n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                  # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra               # make ra the bigger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

find is a loop, not a recursion, so no chain can hit the recursion limit. On the beanstalk sequence above, this version makes zero parent hops: every union(0, i) hangs the single node i under the big root.

Trace DSU(6) through six unions:

Before the last call, the forest looks like this:

    0         4
   / \        |
  1   2       5
      |
      3

In union(3, 5), find(3) walks 3 → 2 → 0, and halving re-points 3 straight at 0 on the way. The size-4 root 0 then adopts the size-2 root 4. Only a root's size means anything: size[2] still says 2, a stale leftover like the cells past the returned length in Foundation: Arrays & Strings.

Invariants: each root's size is the number of nodes in its tree, and two nodes have the same root exactly when the edges so far connect them.

Predict first: after the table, call find(5). What does it return, and what does parent look like afterward?

The edge that closes a loop

union returning False means a and b were already connected. Adding an edge between them creates a second route, so the new edge closes a cycle. That makes undirected cycle detection three lines. LeetCode 684: Redundant Connection gives a tree on nodes 1..n plus one extra edge, and asks for the edge to delete. If several would work, return the one that appears last in the input.

def find_redundant_connection(edges):
    dsu = DSU(len(edges) + 1)             # labels 1..n, and n == len(edges)
    for a, b in edges:
        if not dsu.union(a, b):
            return [a, b]                 # a and b were already connected

print(find_redundant_connection([[1, 2], [1, 3], [2, 3]]))                   # [2, 3]
print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))   # [1, 4]

Why the first failure is the right answer. A tree plus one edge contains exactly one cycle, and deleting any edge of that cycle leaves a tree. Processing edges in input order, the first union that fails is the edge that completes the cycle, which is the cycle edge that appears last in the input. Edges off the cycle never fail. Time O(n α(n)), space O(n). The second example shows why "just return the last edge" is wrong: [1, 5] is last, but it is not on the cycle 1–2–3–4.

Your turn: a graph is a tree when it is connected and has no cycle. Using DSU, write is_tree(n, edges). Predict it for n = 4 with [[0, 1], [0, 2], [0, 3]], and with [[0, 1], [1, 2], [2, 0]].

def is_tree(n, edges):
    if len(edges) != n - 1:
        return False
    dsu = DSU(n)
    return all(dsu.union(a, b) for a, b in edges)

print(is_tree(4, [[0, 1], [0, 2], [0, 3]]))   # True
print(is_tree(4, [[0, 1], [1, 2], [2, 0]]))   # False

Level up: wire everything for the least cost

LeetCode 1584: Min Cost to Connect All Points gives points on a plane. Connecting two points costs their Manhattan distance, |x₁ − x₂| + |y₁ − y₂|. Connect all points, directly or through others, at the least total cost. The cheapest connected network is a minimum spanning tree (MST). Kruskal's algorithm sorts every possible edge by cost and takes each one that joins two different groups. That "different groups" test is union returning True.

def min_cost_connect_points(points):
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            (x1, y1), (x2, y2) = points[i], points[j]
            edges.append((abs(x1 - x2) + abs(y1 - y2), i, j))
    edges.sort()                          # cheapest first
    dsu = DSU(n)
    total = used = 0
    for cost, i, j in edges:
        if dsu.union(i, j):               # skip edges inside one group
            total += cost
            used += 1
            if used == n - 1:
                break
    return total

print(min_cost_connect_points([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]))   # 20

With the points numbered 0–4 in that order:

Four edges connect five points, so the loop stops at 20.

Why taking the cheapest edge between two groups is safe. Say Kruskal takes e = u–v, and X is u's group at that moment. Take a cheapest network N that contains Kruskal's earlier edges; it never needs a cycle, so it is a tree. N has a path from u to v, and that path leaves X through some edge f. Every edge cheaper than e has already been considered and now lies inside a group, so f, which leaves X, costs at least as much as e. For the same reason f is not one of Kruskal's earlier edges. Removing f splits N into two pieces, with u on one side and v on the other, and e joins them again. So N − f + e is connected, costs no more than N, and contains every edge Kruskal has taken so far. Repeat for each edge Kruskal takes, and Kruskal's result is a cheapest network.

Cost: n points give n(n − 1)/2 edges: 499,500 for n = 1,000. Sorting them is O(E log E), about 9.5 million comparisons, plus memory for half a million tuples. For complete graphs like this, Prim's algorithm in its O(n²) array form grows one tree from a start point and never builds the edge list. Kruskal shines when the edges are given and sparse.

What union-find cannot do

• Delete an edge. Unions only merge. Splitting a group is not supported. If all the deletions are known in advance, a common trick processes them backwards as additions.
• Give a path or its length. It knows whether two nodes are connected, not how.
• Directed reachability. "a reaches b" does not mean "b reaches a", so reachability in a directed graph does not split nodes into groups. Union-find is for undirected connectivity.

Final round: no label on the problem

Real problems don't say which tool they want. Translate first (node, edge, question), then pick.

Challenge 1: Rotting Oranges

A grid holds 0 (empty), 1 (fresh orange) and 2 (rotten orange). Every minute, each fresh orange next to a rotten one (up, down, left, right) turns rotten. Return the minutes until no fresh orange is left, or −1 if some can never rot. This is LeetCode 994: Rotting Oranges.

Before peeking:

1. What is a node, what is an edge, and which tool fits?
2. What should [[2, 1, 1], [0, 1, 1], [1, 0, 1]] and [[0, 2]] return?
3. Where does the answer come from, and when is it −1?

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue:
        r, c, t = queue.popleft()
        minutes = t                       # queue order: t never decreases
        for nr, nc in grid_neighbors(grid, r, c):
            if grid[nr][nc] == 1:
                grid[nr][nc] = 2          # mark on discovery (mutates the input)
                fresh -= 1
                queue.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))   # 4
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))   # -1
print(oranges_rotting([[0, 2]]))                             # 0

Challenge 2: Most Stones Removed

Stones sit at distinct integer points. You may remove a stone if another stone still on the board shares its row or its column. What is the largest number of stones you can remove? [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]] gives 5. This is LeetCode 947: Most Stones Removed with Same Row or Column. Up to 1,000 stones.

Before peeking: what are the nodes and edges? In one connected group of stones, how many can you remove, and in what order?

def remove_stones(stones):
    dsu = DSU(len(stones))                # DSU from Step 5
    first_in_row, first_in_col = {}, {}
    for i, (r, c) in enumerate(stones):
        if r in first_in_row:
            dsu.union(i, first_in_row[r])
        else:
            first_in_row[r] = i
        if c in first_in_col:
            dsu.union(i, first_in_col[c])
        else:
            first_in_col[c] = i
    return len(stones) - dsu.groups

print(remove_stones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]))   # 5
print(remove_stones([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]))           # 3

Challenge 3 (boss level): walls you may break

Return to LeetCode 1293 from Step 1: the fewest steps from top-left to bottom-right, moving in 4 directions, breaking at most k walls, or −1. The grid is at most 40 × 40. Write it.

from collections import deque

def shortest_path_with_eliminations(grid, k):
    rows, cols = len(grid), len(grid[0])
    start = (0, 0, k)                     # (row, col, eliminations left)
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        (r, c, left), steps = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return steps
        for nr, nc in grid_neighbors(grid, r, c):
            nleft = left - grid[nr][nc]   # a wall uses one elimination
            state = (nr, nc, nleft)
            if nleft >= 0 and state not in seen:
                seen.add(state)
                queue.append((state, steps + 1))
    return -1

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

Quick fire

Name the tool for each, then check.

1. LeetCode 743: Network Delay Time: a signal leaves node k along directed edges with non-negative travel times. When has every node heard it?
2. LeetCode 785: Is Graph Bipartite?: can the nodes be split into two sides with every edge crossing between them?
3. LeetCode 721: Accounts Merge: accounts that share any email belong to the same person. Merge them.
4. LeetCode 787: Cheapest Flights Within K Stops: the cheapest price from src to dst using at most k stops.
5. LeetCode 127: Word Ladder: the fewest one-letter changes from one word to another, where every word must be in a dictionary.

Cheat sheet

Before moving on, take one problem from this lesson and explain it aloud from a blank editor. Say what a node is and what an edge is, which question is being asked and why that picks the algorithm, what the seen set (or parent array) means at any moment, what it costs in terms of V and E, and which change to the problem would break your choice: weights, negative costs, deletions, or an extra thing to carry.

Next: Graph Traversal for DFS and BFS mechanics in depth, including cycle detection, bipartite checks and cloning a graph. Then Shortest Path Algorithms for Dijkstra, Bellman-Ford and weighted routing.