Graph Day: Reusing the Same Engines Again

Graph day — Course Schedule, Clone Graph, and Word Ladder, with the full follow-up tree on each. Notes:

• Course Schedule's BFS (Kahn's algorithm) doesn't check for cycles directly — it's inferred afterward. A course stuck in a cycle can never reach inDegree == 0, because whatever would unlock it is trapped in the same cycle
• inDegree[nextCourse] -= 1, never inDegree[course] — the course you just popped already earned its zero; it's the next course that just lost a dependency
• DFS cycle detection needs path (still on my current call stack) separate from visited (cleared elsewhere) — a single visited set can't tell those apart, and a diamond-shaped DAG (0→1→3, 0→2→3) proves it: 3 gets visited twice with zero cycles involved
• Clone Graph's dictionary isn't just a visited-set with extra steps — a set can only answer "have I seen this," but you need the actual cloned object back to wire into .neighbors, so the dict does both jobs at once
• Registering a clone before recursing into its neighbors is the key step — this is an undirected graph, so a neighbor can point straight back to a node still mid-clone, and that's an infinite recursion without the early registration
• Disconnected Clone Graph follow-up: the output should be sized by component count, not by how many input nodes you were handed — one entry point per component is enough, since the rest is reachable through .neighbors
• Word Ladder is grid BFS's snapshot-queue trick again, just with neighbors generated on the fly (try all 26 letters at every position) instead of read off a fixed adjacency list
• Bidirectional BFS's real optimization is the swap: always expand whichever side (front or back) is smaller, or the whole benefit of searching from both ends disappears
• Word Ladder II needs a whole BFS level removed from the word set at once, not word-by-word — otherwise the second word in the same level that could reach the same next word sees it as already gone and silently loses a valid parent
• Bug pattern of the day: reusing a variable name for a loop when the original value is still needed later — node got overwritten in the middle of a BFS, word got shadowed inside a recursive backtrack function, and a return [] was placed one indent level too shallow, so it ran after only the first batch instead of after the whole queue was empty. Different variable names, same lesson as last time