Deadlock Detection

Given a wait-for graph, detect if a deadlock exists.

Function

func DetectDeadlock(n int, edges [][2]int) bool

Behavior

• There are n processes labeled 0..n-1.
• Each edge (u, v) means process u is waiting for v.
• Interpret edges as mandatory current waits on exclusive ownership, with no timeout, external release, or preemption. Under this model, a cycle means deadlock. Graphs for multiple interchangeable instances or optional alternatives need more state; this function only detects directed cycles.
• Return true iff the wait-for graph contains a cycle.
• Search disconnected components; a self-loop counts as a cycle. An edge to a previously completed DFS vertex alone does not.

Notes

• Use any cycle detection algorithm (DFS with colors is sufficient).
• n >= 0. Edges with either endpoint outside 0..n-1 are ignored; duplicate valid edges do not change the result. The empty graph returns false.