leetExpert

Module 23 · Graphs

Practice

Practice~2 min

How to practice this module

Graph problems reward choosing the traversal and marking visited correctly. Clone Graph tests BFS with an aliasing trap; Course Schedule and II test cycle detection (Kahn and DFS postorder); the rest are shortest-path and union-find applications. Done when all seven show Solved in the hub.

Problems

Graphs — work them in order; difficulty ascends.

0/7

solved

  1. 1Clone GraphMediumBFS + clone mapWatch for: Returning the original graph is the classic trap — the map must hold clones and every edge must be cloned
  2. 2Course ScheduleMediumCycle detection (Kahn)Watch for: A course graph with a cycle can never finish; track the processed count against the number of courses
  3. 3Course Schedule IIMediumTopological orderWatch for: The order is the peel order of zero-indegree nodes — a partial peel means a cycle, not a valid order
  4. 4Network Delay TimeMediumDijkstraWatch for: The answer is the max of all shortest paths; a node never reached means -1
  5. 5Number of ProvincesMediumUnion-find / componentsWatch for: Count roots, not edges — union rows with a 1 and count distinct parents
  6. 6Redundant ConnectionMediumUnion-find cycle breakWatch for: The edge that joins two already-connected nodes is the redundant one; return the last such edge
  7. 7Min Cost to Connect All PointsMediumMST (Kruskal / Prim)Watch for: A complete graph is O(n^2) edges — stop early once n - 1 edges are in the tree

Cheatsheet

Graphs — Nodes + edges — BFS for short, DFS for components, Union-Find for merges.

Smell → pattern

  • Shortest path, unweightedBFS
  • Connected components / cycleDFS or Union-Find
  • Topological order / course scheduleKahn or DFS postorder
  • Edges stream in; connectivity queriesUnion-Find
  • Grid islands / regionsDFS/BFS flood

Patterns

BFS shortest

Core

Smell: Unweighted (or equal-weight) distance

Queue + dist (or layer count). First time you reach a node is optimal — don’t relax it again. Mark seen when enqueued, not when dequeued, to avoid duplicates.

0L1L2

DFS components

Safe

Smell: Count islands, colour regions, detect cycles

Flood from each unvisited node. Mark visited to avoid revisits. On directed graphs, cycle detection needs a recursion-stack (or colours), not only a visited set.

Union-Find

Reach

Smell: Merge sets; ask ‘same component?’

find(u) with path compression; union by rank/size. Perfect when edges arrive as pairs and you rarely need full adjacency.

union

Topo sort (Kahn)

Careful

Smell: Order tasks with prerequisites

Queue zero-indegree nodes; peel outgoing edges. Cycle ⇔ you finish with fewer than V nodes ordered. DFS postorder is the dual.

0L1L2

Complexity targets

  • BFS / DFS

    Time
    O(V+E)
    Space
    O(V)
    Note
    Adj list assumed

  • Union-Find (α)

    Time
    ≈ O(E α(V))
    Space
    O(V)
    Note
    Nearly linear

  • Kahn topo

    Time
    O(V+E)
    Space
    O(V)
    Note
    Indegree array + queue

Traps

  • Directed vs undirected edges

    Adding both directions on a directed problem invents paths that don’t exist. Match the statement — and build the adj list the same way.

  • Marking visited too late

    In BFS, mark when you enqueue. Marking only on dequeue lets the same node sit in the queue many times and blows time on dense graphs.