Standard Bar Graphs · Topo Sort Problems O(V + E) · O(V)
A batch job runner processes work items whose one-way 'wait for' tickets must never form a loop. The scanner peels the system like an onion: any item nobody waits on (indegree zero) runs and cancels its own outgoing tickets, freeing more items. If the peeling stops with items still stuck holding tickets, a circular wait — a deadlock — is proven.
Input: An integer V and an adjacency list adj where adj[i] lists the items that item i's completion unblocks.
Output: Return true if the directed graph contains a cycle, otherwise false.
1 <= V <= 10^50 <= number of edges <= 2 * 10^50 <= adj[i][j] < VInput: {"V":4,"adj":[[1,2],[3],[3],[]]}
Output: false
Every item eventually reaches indegree zero — the whole queue drains cleanly.
Input: {"V":3,"adj":[[1],[2],[0]]}
Output: true
Each item waits on the next in a closed ring; nothing ever reaches indegree zero.