Graph Exploration Target: 15s
Directed uses 3 colors (gray = on stack = cycle). Undirected just checks visited + skip parent. Don't mix them up.
CYCLE DETECTION — DIRECTED vs UNDIRECTED
────────────────────────────────────────
UNDIRECTED GRAPH:
DFS: if neighbor is visited AND not parent → cycle
Union-Find: if find(u) == find(v) before union → cycle
DIRECTED GRAPH:
DFS with 3 colors:
WHITE (0) = unvisited
GRAY (1) = in current DFS path (on stack)
BLACK (2) = fully processed
If we visit a GRAY node → back edge → CYCLE
Kahn's BFS (topological sort):
If not all nodes processed → cycle exists
KEY DIFFERENCE:
Undirected: any back edge = cycle (skip parent)
Directed: only GRAY (in-stack) back edge = cycle
BLACK (cross/forward edge) is OK!
TEMPLATE:
directed: color[u] = GRAY → visit → color[u] = BLACK
undirected: visited[u] = True, pass parent to avoid
false positive on the edge we came fromType it from memory. Go.