Detect a Cycle in a Directed Graph
Difficulty: Hard · Pattern: Graph DFS · Concept: General Coding (DSA) — Core Patterns to Drill
Given a directed graph as an adjacency list, determine whether it contains a cycle. This isn't just an academic question — a dependency graph (build systems, task scheduling, spreadsheet formulas) with a cycle means "these things depend on each other in a loop," which is exactly the condition that makes a valid execution order impossible to construct at all.
In an undirected graph, "have I seen this node before during this DFS" is enough to detect a cycle. In a directed graph it isn't — DFS can perfectly legitimately revisit a node it already fully finished exploring via a completely different path, and that's not a cycle. The fix is tracking three states per node instead of two: white (untouched), gray (currently being explored, somewhere on the current DFS path), black (fully explored, done). A cycle exists exactly when DFS reaches a node that's currently gray — that's the signal you've looped back onto your own current path, not just revisited an already-finished branch.
Your task: implement has_cycle(graph), where graph is a dict mapping each node to a list of nodes it points to.