Topic 15: Advanced Graphs

Key Intuition: Advanced graph problems include lexicographically smallest topological orders, Eulerian paths, MSTs, and weighted shortest paths, critical connectivity and graph augmentations.

Canonical Questions #

Lexicographic Topological Sorting #

• Find smallest topo order by lex order handling ties – topo ordering modifications

Problems #

1. Alien Dictionary (269) (neetcode link) ⭐️

   This is a modified topo sort. The key part is to understand how to construct the adjacency graph, which is to consider the pairwise elements and make judgements. The interesting part for this is just step 2 below.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

   from collections import defaultdict, deque from typing import List class Solution: def alienOrder(self, words: List[str]) -> str: # Step 1: Initialize data structures # Graph: character -> set of characters it precedes [char that comes after it] (adjacency list) graph = defaultdict(set) # Indegree count of each node (character) -- we care about characters within the alien-alphabet indegree = {c:0 for word in words for c in word} # because not all the characters may be in use # Step 2: Build graph edges (and indegree array) from adjacent pairs for i in range(len(words) - 1): w1, w2 = words[i], words[i+1] # Invalid edge case: Check for prefix case where w1 is longer but w2 is prefix -> invalid if len(w1) > len(w2) and w1.startswith(w2): return "" # Find first differing character for c1, c2 in zip(w1, w2): if c1 != c2: # Add edge c1 -> c2 if not already added if c2 not in graph[c1]: graph[c1].add(c2) indegree[c2] += 1 break # Only first differing character per pair is relevant # Step 3: Topological sort (Kahn's Algorithm) # Start with nodes that have zero indegree queue = deque([c for c in indegree if indegree[c] == 0]) output = [] while queue: c = queue.popleft() output.append(c) for nei in graph[c]: indegree[nei] -= 1 if indegree[nei] == 0: queue.append(nei) # Step 4: If output length differs from unique chars count, cycle detected if len(output) != len(indegree): return "" return "".join(output)

   Code Snippet 1: Alien Dictionary (269) – the graph creation is the interesting part here
   Pattern Extraction

   Core Insight: Each adjacent pair of words gives one directed edge between characters. Build a graph, then topological sort gives the character ordering. Cycle = invalid ordering. Pattern Name: Topological Sort from Implicit Ordering Constraints Canonical Section: Advanced Graphs > Topological Sort Applications Recognition Signals:

   • “Determine character ordering from sorted words”
   • Pairwise comparison gives directed edges
   • Topological sort on the character graph
   • Cycle = invalid ordering

   Anti-Signals:

   • Words are sorted by known alphabet – just read the order
   • Need all valid orderings – enumerate topological sorts (exponential)

   Decision Point: Extract edges from adjacent word pairs, build a directed graph, run Kahn’s algorithm.

   Pitfalls and Misconceptions

   1. Trap: Comparing non-adjacent words. Why: Only adjacent words are guaranteed to give a valid ordering edge. Correction: Only compare words[i] with words[i+1].
   2. Trap: Not detecting the invalid case where a longer word is a prefix of a shorter word. Why: If words[i] is a prefix of words[i+1] but words[i] is longer, the ordering is invalid. Correction: Check: if all characters match up to the shorter word’s length AND len(words[i]) > len(words[i+1]), return "" (invalid).
   3. Trap: Forgetting to include characters with no ordering constraints. Why: These characters are valid parts of the alphabet but have no edges. Correction: Initialise the graph with ALL unique characters from all words.
   Problem Mutations

   1. What if you needed to verify a given ordering? (stress-tests: derivation vs verification) Check each adjacent word pair against the given ordering. \(O(n \cdot L)\).
   2. What if the order were partially specified? (stress-tests: full ordering) Fewer edges, less constrained topo sort. Multiple valid orderings exist.
   3. What if you needed the lexicographically smallest valid ordering? (stress-tests: any valid ordering) Use a min-heap instead of a queue in Kahn’s algorithm to always process the smallest available character first.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Alien Dictionary generated via batch canonical enrichment pass.
   

Eulerian Path & Circuit #

• Reconstruct path covering all edges exactly once – Eulerian Path. We need to be able to analyse the question and realise that Eulerian paths are relevant when self-loops can be tolerated and that the objective is to determine an ordering of the edges that we wish to traverse. That’s why it’s Eulerian path/circuit.

Problems #

1. Reconstruct Itinerary (332)

   What are we traversing? It’s the edges because tickets represent edges and we’re interesting in utilisation of tickets.

   We also know from the question that loops between nodes exist – self-loops are tolerable.

   This aligns with Eulerian path problems where cycles or loops are allowed / common and we must cover every edge, even if path must revisit vertices multiple times along the way.

   Also careful on the tie-breaking rules (the lexical order).

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   from collections import defaultdict, deque class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: graph = defaultdict(list) for src, dest in tickets: graph[src].append(dest) # sort to abide by the lexicographical ordering: for src in graph: graph[src].sort(reverse=True) # TRICK: this also just allows us to directly pop out based on the order we wish. # It's reversed because popping happens from the back of the array itinerary = [] def dfs(airport): # while we have outgoing edges, entertain them all: while graph[airport]: # explore depth first! dfs(graph[airport].pop()) # post-order, we can add it in now itinerary.append(airport) dfs('JFK') return itinerary[::-1]

   Code Snippet 2: Reconstruct Itinerary (332) – Heirholzer's Algo (DFS with lexical ordering for tie-breaking)
   Pattern Extraction

   Core Insight: Euler path: visit every edge exactly once. Use Hierholzer’s algorithm: DFS with edge deletion, append to result in post-order (reverse at the end). Pattern Name: Hierholzer’s Algorithm (Eulerian Path) Canonical Section: Advanced Graphs > Euler Path Recognition Signals:

   • “Use every ticket exactly once” = Euler path
   • Lexicographic ordering = sort adjacency lists
   • Start from a fixed vertex

   Anti-Signals:

   • Visit every NODE once – Hamiltonian path (NP-hard)
   • Shortest path – Dijkstra/BFS

   Decision Point: “Use every edge once” = Euler path/circuit. “Visit every node once” = Hamiltonian (NP-hard). The edge-vs-node distinction is critical.

   Pitfalls and Misconceptions

   1. Trap: Using standard DFS without the post-order trick. Why: Standard DFS can get stuck at dead ends. Hierholzer’s post-order ensures edges from dead ends are placed at the end of the itinerary. Correction: Append to result AFTER all edges from a node are explored (post-order). Reverse at the end.
   2. Trap: Not sorting adjacency lists lexicographically. Why: Need the lexicographically smallest itinerary. Sorting ensures DFS explores the smallest option first. Correction: Sort or use a min-heap for each adjacency list.
   Problem Mutations

   1. What if the graph were undirected? (stress-tests: directed) Same Hierholzer’s algorithm but each edge needs to be “deleted” from both directions.
   2. What if you needed the shortest itinerary (by total edge weight)? (stress-tests: all edges) Different problem. The Euler path uses ALL edges; the shortest path uses the cheapest path.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Reconstruct Itinerary.
   

Minimum Spanning Tree (MST) #

• Build MST with Kruskal or Prim algorithms

Problems #

1. Min Cost to Connect All Points (1584) ;; DONE

   it’s all Manhattan distances so that’s nice. We also know that it’s a completely connected graph and so it’s going to be dense and we can’t employ the usual measures. We have to do MST finding but lazily, so we pick the best midpoint (u) for every node (v) that we try to relax.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Solution: def minCostConnectPoints(self, points: List[List[int]]) -> int: n = len(points) visited = [False] * n dist = [float('inf')] * n dist[0] = 0 # start from point 0 total_cost = 0 for _ in range(n): u = -1 # Determine u: # Pick the unvisited node with the smallest distance as the midpoint (u) for i in range(n): is_first_or_is_closer = (u == -1 or dist[i] < dist[u]) if not visited[i] and is_first_or_is_closer: u = i visited[u] = True total_cost += dist[u] # Update distances to ALL other UNVISITED points (for all v) for v in range(n): if not visited[v]: cost = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]) if cost < dist[v]: dist[v] = cost return total_cost

   Code Snippet 3: Min Cost to Connect All Points (1584)
   Pattern Extraction

   Core Insight: MST on a complete graph. Prim’s or Kruskal’s. Edge weight = Manhattan distance between points. Pattern Name: Minimum Spanning Tree (Prim’s / Kruskal’s) Canonical Section: Advanced Graphs > MST Recognition Signals:

   • “Connect all nodes with minimum total edge weight”
   • Undirected, weighted, complete graph

   Anti-Signals:

   • Shortest path between two nodes – Dijkstra
   • Directed graph – MST doesn’t apply

   Decision Point: Dense graph (\(E = V^2\)) = Prim’s is natural. Sparse graph = Kruskal’s. For complete graphs, Prim’s with a heap avoids materialising all \(O(V^2)\) edges.

   Pitfalls and Misconceptions

   1. Trap: Computing all \(O(n^2)\) edges upfront for Kruskal’s. Why: \(O(n^2 \log n^2)\) sorting. Prim’s avoids this by lazily computing edges. Correction: Use Prim’s: start from any node, push all edges to neighbours into a heap, pop smallest.
   2. Trap: Not using path compression and union by rank in Kruskal’s. Why: Without these, union-find degrades from \(O(\alpha(n))\) to \(O(n)\). Correction: Always use both optimisations.
   Problem Mutations

   1. What if the distance metric were Euclidean? (stress-tests: Manhattan) Same MST algorithm, different weight function.
   2. What if edges were already given (not complete graph)? (stress-tests: complete graph) Kruskal’s is simpler for sparse graphs: sort edges, greedily add non-cycle edges.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Min Cost to Connect All Points.
   

Weighted Shortest Paths #

• Use Dijkstra’s or Bellman-Ford for weighted graph shortest paths

Problems #

1. Network Delay Time (743)

   This is just a classic dijkstra (because edge weights are non-negative), single source we want to find the longest branch from this single source to every other node. Applies for network related problem domains as well.

   Note the use of the 1-idx shimming and splicing here. It’s because our nodes are labelled 1-indexed but we wish to make the code convenient for us to write, hence we just add in a dummy.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   from collections import defaultdict import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = defaultdict(list) for u, v, w in times: graph[u].append((v, w)) # we're going to shim the 0th idx to handle the 1-indexing, then later ignore it dist = [float('inf')] * (n + 1) dist[k] = 0 heap = [(0, k)] # current dist, node (min-pq by distance) while heap: curr_dist, node = heapq.heappop(heap) if curr_dist > dist[node]: continue for nei, w in graph[node]: # if can relax (better alt route): if curr_dist + w < dist[nei]: dist[nei] = curr_dist + w heapq.heappush(heap, (dist[nei], nei)) max_dist = max(dist[1:]) # accounts for the 1-idx shimming return max_dist if max_dist != float('inf') else -1

   Code Snippet 4: Network Delay Time (743)
   Pattern Extraction

   Core Insight: Single-source shortest path from the source node to all others. Use Dijkstra’s algorithm (non-negative weights). The answer is the maximum shortest-path distance across all nodes. Pattern Name: Dijkstra’s Single-Source Shortest Path Canonical Section: Advanced Graphs > Shortest Path (Weighted) Recognition Signals:

   • Weighted directed graph, non-negative weights
   • “Time for signal to reach all nodes” = max shortest path
   • Need the max of all shortest paths

   Anti-Signals:

   • Negative edge weights – use Bellman-Ford
   • Unweighted graph – use BFS
   • All-pairs shortest paths – use Floyd-Warshall

   Decision Point: Non-negative weights = Dijkstra. Negative weights = Bellman-Ford. Unweighted = BFS.

   Pitfalls and Misconceptions

   1. Trap: Not using a min-heap for Dijkstra’s. Why: Without a heap, finding the next closest unvisited node is \(O(V)\) per step, giving \(O(V^2)\) total. Correction: Use heapq with (distance, node) tuples.
   2. Trap: Processing already-finalised nodes from stale heap entries. Why: Dijkstra’s with a heap can pop stale entries. Processing them wastes time. Correction: Skip nodes already in the visited set when popped.
   3. Trap: Forgetting to check if all nodes are reachable. Why: If any node’s distance is inf, the signal never reaches it. Return -1. Correction: if max(dist.values()) = float(‘inf’): return -1=.
   Problem Mutations

   1. What if edge weights could be negative? (stress-tests: non-negative weights) Use Bellman-Ford (\(O(VE)\)).
   2. What if you needed shortest path with at most \(k\) edges? (stress-tests: unlimited edges) Bellman-Ford with \(k\) iterations. Connects to LC 787.
   3. What if the graph were undirected? (stress-tests: directed) Add edges in both directions. Same algorithm.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Network Delay Time generated via batch canonical enrichment pass.
   

2. Cheapest Flights Within K Stops (787)

   This problem is one where we are just given edges and we need to find k-hop cheapest flights from single source to single destination. We could do BellmanFord for K + 1 relaxations or we could do a modified BFS (that includes the current stop count instead of rejecting it on first-visit), either works.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   ## M1: BFS Approach (more performant) from collections import defaultdict, deque class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: graph = defaultdict(list) # Build the adjacency list: u -> (v, cost) for u, v, cost in flights: graph[u].append((v, cost)) # Distance array to keep the minimum cost to reach each node dist = [float('inf')] * n dist[src] = 0 q = deque() q.append((0, src, 0)) #(stops, current node, current cost) while q: stops, node, curr_cost = q.popleft() # If the number of stops exceeds the limit, skip further processing if stops > k: continue for neighbor, price in graph[node]: new_cost = curr_cost + price if new_cost < dist[neighbor]: dist[neighbor] = new_cost q.append((stops + 1, neighbor, new_cost)) return -1 if dist[dst] == float('inf') else dist[dst]

   Code Snippet 5: Cheapest Flights Within K Stops (787) – BFS approach (more performant)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: # single src to single dest dist = [float('inf')] * n dist[src] = 0 # we relax the edges for k + 1 times: for _ in range(k + 1): tmp = dist.copy() for u, v, w in flights: can_relax = dist[u] != float('inf') and dist[u] + w < tmp[v] if can_relax: tmp[v] = dist[u] + w dist = tmp if dist[dst] == float('inf'): return -1 return dist[dst]

   Code Snippet 6: Cheapest Flights Within K Stops (787) – Bellman-Ford for (k + 1) relaxations + snapshotting method
   Pattern Extraction

   Core Insight: Bellman-Ford with \(k+1\) iterations. Or Dijkstra with state (cost, node, stops_remaining). Use PREVIOUS iteration’s distances to avoid using more edges than allowed. Pattern Name: Bellman-Ford with Edge Count Constraint Canonical Section: Advanced Graphs > Shortest Path (Constrained) Recognition Signals:

   • Shortest path with at most \(k\) stops (edges)
   • Positive edge weights

   Anti-Signals:

   • No stop limit – standard Dijkstra

   Decision Point: Stop-constrained shortest path = Bellman-Ford with \(k\) iterations. The edge count constraint is what makes standard Dijkstra insufficient.

   Pitfalls and Misconceptions

   1. Trap: Using current iteration’s distances for relaxation instead of previous. Why: Using current allows paths with more edges than the iteration count, violating the stops constraint. Correction: prev_dist = dist.copy() before each iteration. Relax using prev_dist.
   2. Trap: Using standard Dijkstra without state augmentation. Why: Standard Dijkstra doesn’t track stops. A cheaper path with more stops might block a valid path with fewer stops. Correction: Augment state: (cost, node, stops_remaining).
   Problem Mutations

   1. What if there were no stop constraint? (stress-tests: constrained) Standard Dijkstra. The constraint is the hard part.
   2. What if edge weights could be negative? (stress-tests: positive weights) Bellman-Ford handles negative weights naturally (no negative cycles assumed).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Cheapest Flights Within K Stops.
   

3. TODO Path With Minimum Effort (1631) — Weighted shortest path with state expansions similar to Swim in Rising Water

TODO Network Flow & Critical Connections #

• Determine max flow, min cut, critical edges, or articulation points affecting connectivity

Problems #

1. TODO Critical Connections (1192)
   • this is a HARD question that uses a proprietary algo called Tarjan’s Algo

Graph Enumeration & Counting #

• Count specific graph structures: paths, spanning trees, subgraphs, islands

Problems #

1. Count Sub Islands (1905) This is an islands count, the main idea here is that we have two grids to reference from. A pedestrian approach would be to realise that the rules on what makes an island cell are the same for both the grids, so we don’t need to run the island searching on each grid then do a union of some sort, we just need to check that for every islands’ cell, the other grid is also land.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   from collections import deque, defaultdict class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: """ Because of the rules on what makes a cell part of an island, the rules end up being the same for grid2 and grid1. This means that we can directly just """ islands_two = defaultdict(list) count_two = 0 visited_two = set() m, n = len(grid1), len(grid1[0]) dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] for r, c in ((r, c) for r in range(m) for c in range(n)): if (r, c) not in visited_two and grid2[r][c]: count_two += 1 visited_two.add((r, c)) q = deque([(r, c)]) islands_two[count_two].append((r, c)) while q: cr, cc = q.popleft() for nr, nc in ( (cr + dr, cc + dc) for dr, dc in dirs if 0 <= cr + dr < m and 0 <= cc + dc < n and (cr + dr, cc + dc) not in visited_two and grid2[cr + dr][cc + dc] ): visited_two.add((nr, nc)) q.append((nr, nc)) islands_two[count_two].append((nr, nc)) return sum(1 for island in islands_two if all(grid1[r][c] == 1 for r, c in islands_two[island]))

   Code Snippet 7: Count Sub Islands (1905) – suboptimal solution

   Core re-frame for the optimisation step: Instead of storing then checking, invalidate as you go \(\implies\) JIT, space-saving. We don’t really need to store coordinates here, just need to know if that island is valid.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   from collections import deque, defaultdict class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: m, n = len(grid1), len(grid1[0]) dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid2[i][j] == 0: return grid2[i][j] = 0 # inplace-mod to mark visited by zeroing for dr, dc in dirs: dfs(i + dr, j + dc) # pass 1: we remove the invalid islands: -- so the mismatch between grids. If it's not a match then we just flood-fill to erase the connected component for i, j in ((i, j) for i in range(m) for j in range(n)): if grid2[i][j] == 1 and grid1[i][j] == 0: dfs(i, j) # does dfs-based flood-fill, destroys the island on grid 2 # pass 2: we now count the surviving islands: count = 0 for i, j in ((i, j) for i in range(m) for j in range(n)): if grid2[i][j] == 1: dfs(i, j) # marks as visited, mods in-place count += 1 return count

   Code Snippet 8: Count Sub Islands (1905) – 2-pass space optimised solution

   Pass 1 is the optimization. Instead of storing islands and checking later, you destroy invalid islands as soon as you encounter them. By the time Pass 2 runs, every remaining 1 in grid2 is guaranteed valid

   Pattern Extraction

   Core Insight: When validating one structure against another (grid2 islands vs. grid1 support), destructive pre-filtering eliminates the need to materialize intermediate results. Destroy invalid candidates first, then count what’s left.

   Pattern Name: Destructive Two-Pass Validation

   Canonical Section: Grid Algorithms / In-Place Modification

   Recognition Signals:

   • Two grids: one is the domain (grid2), one is a constraint (grid1)
   • Problem asks “count X in grid2 satisfying property from grid1”
   • Validation is all-or-nothing per connected component (all cells pass or none do)
   • Grid size ≤ 10^3 (safe to modify in-place)
   • Standard approach would store intermediate results (islands, cells)

   Anti-Signals:

   • Original grid must be preserved (use non-destructive visited set)
   • Need to report which cells satisfy property, not just count
   • Grid is read-only or part of a larger data structure
   • Multiple queries on the same grid (precompute, don’t destroy)

   Decision Point: Distinguish from “Post-Traversal Validation” (find all, then check). Key: if invalid islands can be destroyed in-place without losing information for the final answer, pre-filter. If you need to track why each island is invalid (for reporting or tie-breaking), validate after.

   Interviewer Comms: “I’ll make two passes. First, I destroy islands in grid2 that have any cell not supported by grid1—this prunes the search space inline. Second, I count what survives. This avoids materializing intermediate island lists.”

   Pitfalls and Misconceptions

   1. Trap: Store all islands from grid2 in a dictionary, then iterate and check each against grid1 (user’s original approach). Why: Space waste on large grids (up to O(m·n) cells stored). Validation re-iterates cells. Double-pass through the island list. Correction: Pre-filter invalid islands with DFS pass 1; by the time you count in pass 2, every remaining cell is guaranteed valid.

   2. Trap: Use BFS to find grid2 islands, but also track which cells belong to which island number (materializing island IDs). Why: Adds memory overhead and doesn’t add value (you only need to count, not report membership). Correction: Only track visited status; destructively mark cells as 0 to indicate “processed in this island.”

   3. Trap: Check `grid1[i][j] == 1` for every cell during BFS traversal, thinking you need to validate incrementally. Why: Unnecessary; if the island is connected in grid2, either all cells are supported or none are (by 4-connectivity). Checking during traversal is redundant. Correction: Pre-filtering in pass 1 handles this: if any cell of an island fails, destroy the whole island before pass 2.

   4. Trap: Forget to mark starting cell as visited in DFS two-pass. Why: Can lead to infinite recursion on the same cell. Correction: Set `grid2[i][j] = 0` immediately upon entering DFS, before recursing.

   5. Trap: Use only one pass, checking `grid1[i][j]` during the counting phase. Why: Inefficient; you’re checking the same cells twice (once to identify island bounds, once to validate). Correction: Two passes separate concerns: invalidate first, then count.

   Problem Mutations

   1. What if: You must return the coordinates of cells in each sub-island, not just count. Stress test: Can’t destroy grid2 (need it to report coordinates). Must store cells or use non-destructive visited set. Switch to BFS with island materialization; DFS two-pass breaks.

   2. What if: grid1 is updated after some queries (online version). Stress test: Pre-filtering is invalid (grid1 changed). Must re-validate each query. DFS two-pass doesn’t generalize; use post-traversal checking instead.

   3. What if: Find the largest sub-island by area. Stress test: DFS two-pass requires a third pass or inline size tracking during pass 2. BFS can track size incrementally. Both work; DFS is slightly more cumbersome.

   4. What if: Both grids are sparse (represented as lists of coordinates, not 2D arrays). Stress test: Neither DFS nor BFS scales well with sparse representation. Use adjacency list + BFS on sparse graph.

   5. What if: grid2 has additional constraints (e.g., each sub-island must be ≥ 5 cells). Stress test: Must track size. DFS two-pass still works; pass 2 counts only if size ≥ 5. BFS also works.

   AI usage disclosure Claude Sonnet 4.6 · coaching

   This canonical entry was drafted during a coaching session on LC 1905 (Count Sub-Islands). The user's BFS solution was correct but space-inefficient. The DFS two-pass approach was highlighted as the optimization: destructive pre-filtering eliminates O(m·n) list storage and re-validation overhead. Dropdowns emphasize the pattern (destructive pre-filtering for all-or-nothing validation) and common pitfalls (materializing islands, redundant validation, forgetting to mark cells visited). Mutations stress-test scenarios where DFS two-pass breaks (need original grid preserved, online queries).
   

2. TODO Number of Distinct Islands (694) (paid)

Graph Augmentation and Supergraphs #

• Create or augment super graphs by adding vertices or edges to model constraints or extended problems
• Typical use includes adding virtual nodes, modelling state spaces, or building layered graphs for dynamic programming on graphs

Problems #

1. Word Ladder (127)

   This is a shortest path problem that feels like an edit distance kind, but it’s a graph traversal. We need to be able to use wildcards and we can create a lookup table for pattern to words which we build by replacing each character in a word with * and mapping those patterns to possible words. Doing so reduces the adjacency connection lookup from \(O(N^{2})\) to \(O(L N)\), where L is word length. Also take note that we only want to reach each node (pattern) once in the overall procedure, so we silence it after we reach it.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

   from collections import defaultdict, deque class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: if endWord not in wordList: return 0 L = len(beginWord) # better mapping: pattern_to_words = defaultdict(list) for word in wordList: for i in range(L): pattern = word[:i] + "*" + word[i + 1:] pattern_to_words[pattern].append(word) # now we run BFS: queue = deque([(beginWord, 1)]) # word, level visited = {beginWord} while queue: word, level = queue.popleft() for i in range(L): pattern = word[:i] + "*" + word[i + 1:] for nei in pattern_to_words[pattern]: if nei == endWord: return level + 1 if nei not in visited: visited.add(nei) queue.append((nei, level + 1)) # NB: prevents repeat lookups, we silence that pattern check so that each pattern is used only once per search. pattern_to_words[pattern] = [] return 0

   Code Snippet 9: Word Ladder (127)

   In some ways, this question involves a graph expansion / modification as well.

2. Swim in Rising Water (778)

   There’s a few ways to do this. For one, we can view this as a modification to the classic dijkstra approach where we prioritise the lowest elevations first (since we can teleport as we wish) It turns Dijkstra’s into a “min-max” path problem. Else we could also see it in a kruskal-like approach where the max height between two points on the grid is seen as the edge weight and we search for an MST such that first and last cells are connected. If imagination fails us, we can also exploit the monotonicity of the answer space and do a binary search like approach.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150

   # MODIFIED DIJKSTRA APPROACH: prioritise the lowest elevation ones to handle first from collections import defaultdict, deque import heapq class Solution: def swimInWater(self, grid: List[List[int]]) -> int: # start from S, end at D, fastest hops possible # prioritise the smallest elevation so far ROWS, COLS = len(grid), len(grid[0]) DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)] visited = [[False] * COLS for _ in range(ROWS)] # GOTCHA: we can't assume that the first will be elevation = 0, so we have to read it from the grid. heap = [(grid[0][0], (0,0))] # (elevation, coordinate) visited[0][0] = True while heap: t, (r, c) = heapq.heappop(heap) # first reach of the target if r == ROWS - 1 and c == COLS - 1: return t for row, col in ((r + dr, c + dc) for dr, dc in DIRS if 0 <= r + dr < ROWS and 0 <= c + dc < COLS and not visited[r + dr][c + dc] ): # visit it: visited[row][col] = True # NOTE: if we're accessing this later in time (e.g. cuz it was an island or something) then we need to respect the current time that's why we need to max this like so: new_time = max(t, grid[row][col]) heapq.heappush(heap, (new_time,(row, col))) # this runs in O(n^{2} \log n) time because each heap ops is log n time and each cell in grid is considered once (hence the n^{2}). Space use is just O(n^{2}) # M2: KRUSKAL-LIKE APPROACH: class UnionFind: def __init__(self, n): # Initialize parent list where each node is its own parent (representative) self.parent = list(range(n)) def find(self, x): # Find the root parent (representative) of x with path compression # Path compression flattens the tree by making each node point directly to the root if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # Union the sets containing x and y # Returns False if x and y already belong to the same set px, py = self.find(x), self.find(y) if px == py: return False # already connected self.parent[px] = py # attach one tree under the other return True class Solution: def swimInWater(self, grid): n = len(grid) if n == 1: # handle the trivial return case return 0 # Helper to convert 2D grid coordinates (r, c) into 1D index for Union-Find def idx(r, c): return r * n + c edges = [] # list of edges in the graph as (weight, node1, node2) # Generate edges between all pairs of adjacent cells (right and down neighbors) # Weight of edge = max elevation of the two nodes (cells) for r in range(n): for c in range(n): if r + 1 < n: weight = max(grid[r][c], grid[r+1][c]) edges.append((weight, idx(r, c), idx(r+1, c))) if c + 1 < n: weight = max(grid[r][c], grid[r][c+1]) edges.append((weight, idx(r, c), idx(r, c+1))) # Sort all edges by ascending weight (height) edges.sort() uf = UnionFind(n * n) # initialize union-find for all nodes # Process edges in order of increasing weight for height, u, v in edges: uf.union(u, v) # connect the two nodes in the union-find structure # After each union, check if start (top-left cell) and end (bottom-right) are connected if uf.find(0) == uf.find(n * n - 1): # The earliest time when the start and end belong to the same connected component # is the required minimal water level return height # M3: Binary Search approach. from collections import deque class Solution: def swimInWater(self, grid): n = len(grid) def can_reach(t): """ Helper function to check if it's possible to swim from (0,0) to (n-1,n-1) if water level is 't' (i.e., you can only enter cells where elevation <= t). Uses BFS for reachability. """ # If the starting cell is higher than t, cannot start swimming yet if grid[0][0] > t: return False visited = [[False]*n for _ in range(n)] queue = deque([(0, 0)]) visited[0][0] = True # BFS to explore reachable cells under water level t while queue: r, c = queue.popleft() # Check if we've reached the target cell if r == n - 1 and c == n - 1: return True # Explore 4-directional neighbors for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nr, nc = r + dr, c + dc # Check boundaries and if we can move into the neighbor cell if (0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] <= t): visited[nr][nc] = True queue.append((nr, nc)) # If BFS finishes without reaching end, return False return False # The minimum time to wait is at least the max of start and end elevations left, right = max(grid[0][0], grid[-1][-1]), n * n - 1 # Binary search for the minimum water level t that allows swimming through while left < right: mid = left + (right - left) // 2 if can_reach(mid): # If reachable, try lower water levels right = mid else: # If not, increase water level left = mid + 1 return left

   Code Snippet 10: Swim in Rising Water (778)
   Pattern Extraction

   Core Insight: Minimax path: minimise the maximum cell value along any path from \((0,0)\) to \((n-1,n-1)\). Modified Dijkstra where path cost = max cell value (not sum). Or binary search on answer + BFS. Pattern Name: Dijkstra on Bottleneck (Minimax Path) Canonical Section: Advanced Graphs > State-Space Augmented Search Recognition Signals:

   • Grid pathfinding where cost = MAX cell value along path
   • Minimise the maximum (minimax)

   Anti-Signals:

   • Cost = sum of cells – standard Dijkstra
   • All cells same value – just BFS reachability

   Decision Point: Minimax path = Dijkstra with new_cost = max(dist[curr], grid[nr][nc]) instead of sum.

   Pitfalls and Misconceptions

   1. Trap: Using sum-based Dijkstra. Why: The bottleneck is the max cell, not the sum. Different objective. Correction: new_dist = max(dist[curr], grid[nr][nc]).
   2. Trap: Not recognising this as a graph problem (treating it as DP). Why: The grid has 4-directional movement (including going “backward”). DP requires a DAG structure. Correction: Use Dijkstra or binary search + BFS.
   Problem Mutations

   1. What if costs were edge-based instead of node-based? (stress-tests: node costs) Same algorithm but the edge weight determines the path cost.
   2. What if you could wait at any cell? (stress-tests: instantaneous movement) Waiting until the water level reaches the cell’s elevation IS the problem’s semantics. The max-based Dijkstra models this.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Swim in Rising Water.
   

3. Shortest Path in a Grid with Obstacles Elimination (1293) — Graph augmentation using state expansions

4. Minimum Cost to Make at Least One Valid Path in a Grid (1368) — Edge cost modifications and augmentations

5. Minimum Cost Path with Teleportations (3651)

6. Minimum Cost Path with Edge Reversals (3650)

   See essay plan for this

   Revised Essay Plan: Minimum Cost Path with Edge Reversals

   Problem Context: We are given a directed, weighted graph with nodes labeled from `0` to `n-1` and edges `(u, v, w)` representing a directed edge from `u` to `v` with cost `w`. Each node has a “switch” that can be used at most once to reverse an incoming edge upon arrival at that node, enabling a traversal along the reversed edge at double the original cost (`2 * w`).

   Intuition and Approach

   This problem extends shortest path computation (like Dijkstra’s algorithm) with the added complexity of edge reversals that can only be used once per node, and only on arrival.

   Key Ideas

   1. Directed Graph and Reversals:

      • The graph is directed and weighted.
      • Reversed edges can be traversed at double cost but only by activating the node’s switch, which can be used at most once per node.

   2. Modelling Reversals as Extra Edges:

      • We build two graphs:
        • `graph[u]` for normal (forward) edges `(u → v)`.
        • `rev_graph[v]` for incoming edges `(u → v)`, reversed as `(v → u)` with cost doubled (`2 * w`).
      • This enables considering traversing reversed edges from node `v` if you choose to activate that node’s switch.

   3. Dijkstra Without Explicit State Tracking:

      • Instead of modeling per-node switch usage explicitly, we merge these edges and run a standard Dijkstra algorithm over the combined graph (normal + reversed edges).
      • The algorithm computes the minimal cost to reach each node considering the possibility of using reversed edges anywhere in the path.
      • This works efficiently and solves the problem correctly under the problem constraints or test data.

   4. Tradeoff:

      • This approach does not explicitly enforce the “only once per node” switch usage constraint.
      • However, due to cost structure and graph traversal, the shortest path computed often naturally respects the constraint or finds the true minimum.
      • For full rigor, a stateful Dijkstra tracking per-node switch usage (`dist[node][switch_used_flag]`) can be used but increases complexity.

   5. Simplification Benefits:

      • The simplified approach is easier to implement, faster in practice, and suffices for large input constraints.
      • It effectively handles both normal traversals and reversal moves as edges with different costs.

   Summary of Solution Steps

   • Build `graph` and `rev_graph` from input edges.
   • Initialize distance array with infinities.
   • Perform Dijkstra’s algorithm on combined edges:
     • Traverse normal edges at cost `w`.
     • Traverse reversed incoming edges at cost `2 * w`.
   • Return minimal cost to reach node `n-1` or `-1` if unreachable.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

   import heapq from collections import defaultdict class Solution: def minCost(self, n: int, edges: List[List[int]]) -> int: graph = defaultdict(list) rev_graph = defaultdict(list) # just need to have this extension. for u, v, w in edges: graph[u].append((v, w)) rev_graph[v].append((u, w)) # store incoming edges dist = [float('inf')] * n dist[0] = 0 heap = [(0, 0)] # (cost, node) while heap: cost, u = heapq.heappop(heap) if u == n - 1: return cost if cost > dist[u]: # ignore continue # Normal outgoing edges for v, w in graph[u]: ncost = cost + w # if ncost < dist[v]: dist[v] = ncost heapq.heappush(heap, (ncost, v)) # Reversed incoming edges (switch at u) for v, w in rev_graph[u]: ncost = cost + 2 * w if ncost < dist[v]: dist[v] = ncost heapq.heappush(heap, (ncost, v)) return -1

SOE #

• Incorrect lex order tie handling
• Lack of path compression in union-find
• PQ misuse in shortest path calculations
• Comprehension errors :
  • mistaking longest source to multiple destination shortest path vs MST finding (e.g. like in “Network Delay Time (743)”).

Bellman Ford #

Here’s some gotchas related to bellman ford.

# of iterations associated with the number of edges #

When we run bellman ford, we are relaxing edges. At the end of the \(k^{ th }\) iteration, we have \(k-1\) edges that have been relaxed (and \(k\) edges with the right distance).

TRICK/GOTCHA: Use the Snapshotting Trick to avoid Buffer/Copy Distance Array During Relaxation #

When relaxing in Bellman-Ford for a bounded number of edges (or stops), always use a separate temporary copy for updates within each iteration.

This avoids the “parallel edge confounding” where an update in the current round might incorrectly use a value that was just relaxed, effectively allowing more than the intended number of edges (stops) in a path. This only matters when we’re concerned about being strict about the number of relaxations that exist within a particular round of relaxations.

Always base each round’s relaxations only on the previous round’s distances.

Decision Flow #

• Dependency resolution with lex constraints? → Topo sort + priority structure
• Edge covering in graphs? → Eulerian path
• Weighted connectivity? → MST and DSU
• Weighted shortest path? → Dijkstra / Bellman-Ford

Summaries, Style, Tricks and Boilerplate #

Boilerplate #

Topo-sorting Algorithms: #

• 1. Classic DFS-Based Topological Sort (Directed Graphs)
  • For every unvisited node, perform a DFS.
  • ref for BFS, ref for DFS
  • On exit (i.e., after exploring all descendants), push the node to a stack or prepend it to an output list.
  • The resulting list (reversed) is the topological order.

• 2. Kahn’s Algorithm (BFS with In-degree)
  • ref notes and boiler plate here
  • Calculate the in-degree for each node.
  • Start with all nodes of in-degree 0 (no prerequisites).
  • While the queue is not empty:
    • Pop a node, add it to the topo order.
    • For each outgoing edge to neighbor:
      • Decrement neighbor’s in-degree.
      • If in-degree becomes 0, enqueue neighbor.
  • If you cannot include all nodes, the graph contains a cycle.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

  from collections import defaultdict, deque from typing import List def kahn_topological_sort(num_nodes: int, edges: List[List[int]]) -> List[int]: """ Generic Kahn’s Algorithm for Topological Sorting. Args: num_nodes: number of vertices (0 to num_nodes-1) edges: list of [u, v] meaning there is a directed edge u → v Returns: topo_order: A list of vertices in topologically sorted order. If there is a cycle, returns an empty list. """ # Step 1: Build adjacency list and in-degree array adj = defaultdict(list) in_degree = [0] * num_nodes for u, v in edges: adj[u].append(v) in_degree[v] += 1 # Step 2: Initialize queue with nodes having in-degree 0 queue = deque([i for i in range(num_nodes) if in_degree[i] == 0]) topo_order = [] # Step 3: Process nodes with in-degree 0 while queue: node = queue.popleft() topo_order.append(node) # Reduce in-degree for all neighbors for neighbor in adj[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) # Step 4: Check if topological sort is possible (no cycle) if len(topo_order) == num_nodes: return topo_order # Valid topological order else: return [] # Cycle detected → no valid topological ordering

  Code Snippet 11: Topological Sorting Algorithms

• 3. Modified BFS with Priority Queue
  • Variant of Kahn’s algorithm.
  • Instead of an ordinary queue, use a priority queue (min-heap or max-heap) to always select the lex smallest/largest in-degree 0 node.
  • Useful when a specific order is required (e.g., lexicographically smallest topological order).

• 4. Enumerating All Topological Sorts (Backtracking)
  • Recursively:
    • For all available in-degree 0 nodes at the current step:
      • Add node to partial order, decrease in-degrees accordingly.
      • Recurse.
      • Backtrack.
  • Generates all possible topological sorts.
  • Algorithmic complexity is high (factorial in the number of nodes for highly connected DAGs).

• 5. Matrix Methods (Academic)
  • Maintain adjacency matrix.
  • Iteratively remove nodes/columns with all zero entries (no incoming edges).
  • The removal order gives a possible topological order.

• 6. Level-based (Layered) Traversal
  • Remove all in-degree 0 nodes as a “layer.”
  • Repeat on the residual graph.
  • Each layer can be processed in parallel.
  • Produces a series of layers, not necessarily a linear topo sort (but can be linearized if needed).

• Summary Table: Topological Sort Algorithms

  Algorithm	Can Detect Cycles	Produces Topo Order	Notes
  DFS with Rec Stack/Coloring	Yes	Yes	Canonical, easy to implement
  Kahn’s Algorithm (BFS In-degree)	Yes	Yes	Canonical, popular in interviews
  Modified Kahn’s with Priority Queue	Yes	Yes	For lex order or weighted DAGs
  Enumerating All Topo Sorts	-	Yes (all orders)	Higher complexity, not often practical
  Matrix Method	Yes	Sometimes	Theoretical/academic cases
  Level-based Traversal	-	Layers	Good for parallel processing

Pathfinding: Bellman-Ford Algo (\(O(VE)\) ) #

• the relax function is the most important part here: we iterate through all the edges for every relaxation attempt – this involves trying to see if there’s a better alternative path (if dist[u] + w < dist [v])
  • it matters how many relaxations we do: k nodes mean there should be simple path of (k - 1) edges so we should be doing relaxations for (k - 1) times at most – Back to graph theory foundations where “a directed graph with n nodes and without any cycles will have a shortest path from s to d using at most (n - 1) edges (simple path)”
    • optimisation: we can do a quick check to see if any of the distances were NOT updated – which would imply that it’s safe to stop doing relaxations and we can early exit
  • cycle check: doing the k th run can help to check if there are negative-weight cycles
• can’t handle negative cycles, alright if negative edges exist.
• outer iteration is for (n - 1) times (i.e. we relax (n - 1) times).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def bellman_ford(n, edges, src):
    """
    Bellman-Ford: works with negative edges, but no negative cycles.
    Returns (has_no_negative_cycle, distances, parents).
    """
    dist = [float('inf')] * n
    parent = [None] * n
    dist[src] = 0

    for _ in range(n - 1):
        updated = False # allows us to early return if we don't update anything anymore.
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                updated = True
        if not updated:
            break

    # Cycle detection: if I can still relax once more (nth iteration) then I know that there's a cycle.
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return (False, [], [])
    return (True, dist, parent)

Pathfinding: Dijsktra’s Algorithm (\(O(E log V)\)) #

Applies to general graphs with non-negative edges

Relaxes edges in the “right order” exploits the greedy property related to the triangle inequality

Relaxation is the same as in Bellman-Ford.

Parent tracking is needed to do the path-generation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import heapq
from collections import defaultdict

def dijkstra(n, edges, src):
    """
    Dijkstra: shortest paths from src in weighted graph with non-negative weights.
    Returns dist (shortest distances), parent (for path reconstruction).
    Key idea is to keep a min-heap and explore following the shortest distance edge.
    """
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))

    dist = [float('inf')] * n
    dist[src] = 0
    parent = [None] * n # for parent path construction
    heap = [(0, src)]

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # Already found a shorter path
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, parent

Pathfinding: Floyd-Warshall in \(O(V^{3})\) - All pairs shortest path #

Distance Matrix: Because we care about all-pairs, we end up trying to find out values for a distance matrix, that’s why we have a 2D distance matrix. This is helpful because we can do an easy cycle-check: the diagonals are self-loops and should always be 0, if for any reason they are < 0 then we have negative loops – here’s the negative cycle check

The relaxation is something like Bellman-Ford but slightly different. We take for every intermediate node k, consider two pairs of source and destination: i and j and we try to relax it. This means that the relative distances have to be known AND we can relax only if the path via k is a better path.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

def floyd_warshall(n, edges):
    """
    Floyd-Warshall Algorithm: Computes shortest paths between all pairs of vertices.

    Args:
        n (int): Number of vertices in the graph (0-based indexing).
        edges (List[Tuple[int, int, int]]): List of edges (u, v, w).

    Returns:
        dist (List[List[float]]): n x n matrix with shortest path distances.
                                  dist[i][j] = shortest distance from i to j,
                                  float('inf') if no path exists.
        has_negative_cycle (bool): True if a negative cycle is detected; False otherwise.
    """
    # Initialize distance matrix
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0  # Distance to self is zero

    # Set initial values based on edges
    for u, v, w in edges:
        dist[u][v] = w  # Directed edge from u to v with weight w

    # Floyd-Warshall main iteration
    for k in range(n): # k: candidate for intermediate node
        for i in range(n):
            for j in range(n):
                known_dists = dist[i][k] != float('inf') and dist[k][j] != float('inf')
                # If both distances are known, attempt relaxation via k, the intermediate node we consider
                if known_dists:
                    # if can relax:
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]

    # Check for negative weight cycles, if any of the cells on the diagonals are negative (they should be 0 if no cycles)
    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))                                                                 (floyd_warshall_algo_negative_cycle_check)

    return dist, has_negative_cycle


# Example usage:
if __name__ == "__main__":
    n = 4
    edges = [
        (0, 1, 5),
        (0, 3, 10),
        (1, 2, 3),
        (2, 3, 1)
    ]

    dist_matrix, negative_cycle = floyd_warshall(n, edges)

    if negative_cycle:
        print("Graph contains a negative weight cycle.")
    else:
        print("Shortest distances between all pairs:")
        for row in dist_matrix:
            print(['INF' if x == float('inf') else x for x in row])

Pathfinding: Topological Sort (and shortest/longest path in DAG) #

• not every directed graph will have a topological ordering (esp if there are cycles then there’s a cyclic dependency)
• we can do a post-order DFS to get a topo sort
• we can do a Kahn’s algo to do the DFS also

• Find single source shortest path in DAG

  • find the topo sort then relax in the order of topo sort

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

    from collections import defaultdict, deque def dag_shortest_path(n, edges, src): """ Shortest paths in weighted DAG from src using topological sort. """ graph = defaultdict(list) indegree = [0]*n for u, v, w in edges: graph[u].append((v, w)) indegree[v] += 1 # Kahn's topo sort (BFS style) topo = [] q = deque([u for u in range(n) if indegree[u]==0]) while q: u = q.popleft() topo.append(u) for v, _ in graph[u]: indegree[v] -= 1 if indegree[v] == 0: q.append(v) dist = [float('inf')] * n parent = [None]*n dist[src] = 0 for u in topo: for v, w in graph[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w parent[v] = u return dist, parent # For longest path in DAG: Just negate all w before using above.

• DAG longest path: negate then find single source shortest path

Pathfinding: Eulerian Pathfinding via Hierholzer’s Algorithm #

• The key idea behind it:

  1. We build an adjacency list from source to destinations
  2. for each node, we sort the neighbours so that the lexicographical ordering will be respected (this helps in tie-breaking)
  3. then we DFS such that:
     1. we recursively visit neighbours and removing edges as we go
     2. we append the nodes to the itinerary when we can’t go further – this makes it a post-order traversal (which also will give things in reverse order)
  4. reverse the topo order that we see. This is because a dfs approach ends being post-order so the schedule we get is in reversed order!

• a good example of this is in the problem “Reconstruct Itinerary (332)”:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

  from collections import defaultdict, deque class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: graph = defaultdict(list) for src, dest in tickets: graph[src].append(dest) # sort to abide by the lexicographical ordering: for src in graph: graph[src].sort(reverse=True) # TRICK: this also just allows us to directly pop out based on the order we wish. itinerary = [] def dfs(airport): # while we have outgoing edges, entertain them all: while graph[airport]: # explore depth first! dfs(graph[airport].pop()) # post-order, we can add it in now itinerary.append(airport) dfs('JFK') return itinerary[::-1]

Pathfinding: Finding Shortest Path #

• Undirected Graphs

  • we can use BFS and track the parents of each node. Then walking up the parent gives the shortest path tree

    NOTE: DFS parent paths will form a tree but they’re not the shortest path tree

• Directed Graphs

  • BFS/DFS won’t help us cover all the paths, that’s the main reason we can’t just re-purpose them (other than to just use it to visit all nodes / edges in the graph).
  • also BFS will help us only find the number of hops between 2 nodes so if the distances are different (encoded using weighted edge) then we can’t use BFS.

MST-finding: Prim’s Algorithm (\(O(E logV)\) ) #

This is a additive approach to finding MST that relies on the cut property: shortest edge in cycle will appear in MST. We’re picking the min-edge from the currently building tree.

Because this builds up from an existing component, it won’t work when we have to deal with forests (multiple disjoint components), that’s the reason it’s important to also know Kruskal’s Algo.

We exploit the fact that for any cut for vertices involving cycles in the original graph, we’re going to have the smallest edge in the MST.

So it will run in \(O(E logV)\) time

Prim’s algo is better for dense graphs because it’s better to iterate through the neighbours instead of the edges when making the greedy-choices.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import heapq
from collections import defaultdict

def prim_mst(n, edges):
    """
    Prim's Algorithm to find MST of a weighted undirected graph.

    Args:
        n (int): Number of vertices (0-based indexing).
        edges (List[Tuple[int, int, int]]): List of edges (u, v, weight).

    Returns:
        mst_edges (List[Tuple[int, int]]): Edges included in the MST.
        total_weight (int or float): Total weight of MST.
    """
    # Build adjacency list from edges
    # graph[node] = list of (neighbor, weight)
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))  # include this if it's an undirected graph

    total_weight = 0              # Total weight of MST
    mst_edges = []                # To store MST edges as (u, v)
    visited = [False] * n         # Track visited/added vertices

    # Min-heap to pick edge with smallest weight
    # Stores tuples like: (weight, from_vertex, to_vertex)
    min_heap = [(0, -1, 0)]      # Start from vertex 0, no parent hence -1

    while min_heap:
        weight, u, v = heapq.heappop(min_heap)

        if visited[v]:
            continue
        visited[v] = True

        if is_not_start:=(u != -1):
            # Add edge only if v is not the start node (u==-1 means start)
            mst_edges.append((u, v))
            total_weight += weight

        # Add all edges from v to heap if the destination is unvisited
        for to_neighbor, edge_weight in graph[v]:
            if not visited[to_neighbor]:
                heapq.heappush(min_heap, (edge_weight, v, to_neighbor))

    return mst_edges, total_weight

# Example usage
if __name__ == "__main__":
    n = 5
    edges = [
        (0, 1, 2), (0, 3, 6),
        (1, 2, 3), (1, 3, 8),
        (1, 4, 5), (2, 4, 7),
        (3, 4, 9)
    ]

    mst, total = prim_mst(n, edges)
    print("Edges in MST:")
    for u, v in mst:
        print(f"{u} - {v}")
    print("Total weight:", total)

MST-finding: Kruskal’s Algorithm (\(O(ElogV)\)) #

• we wish to do additive inclusion of edges – we sort the edges by weight and consider them in ascending order of weights – this is the most important part
  • if both nodes are in the same blue tree, then we colour the edge red, else we colour that edge blue
  • so this becomes a Union Find operation, where we connect two nodes if they are in the same blue tree
• runs in \(O(E log V)\) time

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

class DisjointSet:
    """
    Disjoint Set Union (Union-Find) data structure with path compression and union by rank.
    Used to efficiently detect cycles while building MST.
    """
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        root = u
        # Step 1: Find root
        while self.parent[root] != root:
            root = self.parent[root]

        # Step 2: Path compression - point all nodes to root
        while self.parent[u] != root:
            next_u = self.parent[u]
            self.parent[u] = root
            u = next_u

        return root

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u == root_v:
            return False
        if self.rank[root_u] < self.rank[root_v]:
            self.parent[root_u] = root_v
        elif self.rank[root_v] < self.rank[root_u]:
            self.parent[root_v] = root_u
        else:
            self.parent[root_v] = root_u
            self.rank[root_u] += 1
        return True

def kruskal_mst(n, edges):
    """
    Kruskal's algorithm to compute MST of a weighted undirected graph.

    Args:
        n (int): Number of vertices.
        edges (List[Tuple[int, int, int]]): List of edges (u, v, weight).

    Returns:
        mst_edges (List[Tuple[int, int, int]]): List of edges included in MST.
        total_weight (int or float): Sum of weights in MST.
    """
    # Sort edges by weight (non-decreasing order)
    edges = sorted(edges, key=lambda x: x[2])

    dsu = DisjointSet(n)
    mst_edges = []
    total_weight = 0

    for u, v, w in edges:
        if dsu.union(u, v):
            mst_edges.append((u, v, w))
            total_weight += w
            if len(mst_edges) == n - 1:  # MST complete
                break

    return mst_edges, total_weight

# Example usage:
if __name__ == "__main__":
    n = 6
    edges = [
        (0, 1, 4), (0, 2, 4), (1, 2, 2), (1, 0, 4),
        (2, 0, 4), (2, 1, 2), (2, 3, 3), (2, 5, 2),
        (2, 4, 4), (3, 2, 3), (3, 4, 3), (4, 2, 4),
        (4, 3, 3), (5, 2, 2), (5, 4, 3),
    ]
    mst, total = kruskal_mst(n, edges)
    print("Edges in MST:")
    for u, v, w in mst:
        print(f"{u} - {v} with weight {w}")
    print("Total weight:", total)