Advanced Graphs: Euler Paths, Bridges & SCCs

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Euler path = use every EDGE once. Bridge = an edge whose removal splits the graph. SCC = a largest group of vertices that all reach each other (directed).

   #1
2. ↯use it when

   "Use every ticket once" → Hierholzer. "Critical connection" → low-link DFS. "Reach each other" → SCC. Ratios → weighted graph. "Fewest buses" → BFS over buses.

   #2
3. { }template

   Hierholzer: visit(u): while u has unused edges, visit(next); then route.add(u). Reverse the route at the end.

   #3
4. { }template

   Bridges: tin[u] = low[u] = timer++; back edge → min(low[u], tin[v]); after child → min(low[u], low[v]); bridge iff low[v] > tin[u].

   #4
5. O( )cost

   Hierholzer O(E) (O(E log E) with min-heaps). Bridges, cut vertices, SCCs: O(V + E). Bus Routes over buses: O(Σ route lengths).

   #5
6. !trap

   Greedy "smallest next airport" can hit a dead end. Add an airport only when it's STUCK, then reverse — that splices the loops in.

   #6
7. !trap

   Bridges: skip the parent edge, use > for bridges but ≥ for cut vertices, and the root is a cut vertex only with 2+ DFS children.

   #7
8. !trap

   Recursive DFS on a 10⁵-long chain can overflow Java's stack. Name the risk and offer the explicit-stack version.

   #8
9. ✦pro tip

   Ratios: a → b carries a/b and b → a carries b/a. Multiply along any path. A variable never seen → -1.0, even for x / x.

   #9
10. ✦pro tip

    Kosaraju = finish order, then DFS on the REVERSED graph, latest finisher first. Each DFS collects exactly one SCC.

    #10

Shaky on a card? Open the chapter or flip its recall cards.