Dependency Cycle Detection (Deadlock)

You are given a set of resources that may depend on one another. A circular dependency chain would cause a deadlock, so your task is to determine whether any such cycle exists in the dependency graph.

Requirements

• The input is a list of lists L, where L[i] is the list of all resources that resource i directly depends on. Resources are identified by their index (0‑based).
• The graph may consist of a single connected component or several disconnected components.
• Return True if the directed graph contains at least one cycle; otherwise return False.

Function Signature

def has_cycle(dependencies: List[List[int]]) -> bool:

Examples

Example 1

Input:  dependencies = [[1, 2], [2], [0]]
Output: True

Explanation: Resource 0 depends on 1 and 2, resource 1 depends on 2, and resource 2 depends on 0. The path 0 → 2 → 0 forms a cycle.

dependencies = [[1, 2], [2], [0]]

true

Example 2

Input:  dependencies = [[1], [2], []]
Output: False

Explanation: Resource 0 depends on 1, resource 1 depends on 2, and resource 2 has no dependencies. The graph is a simple chain with no cycles.

Example 3

Input:  dependencies = [[1], [0]]
Output: True

Explanation: Resource 0 depends on 1 and resource 1 depends on 0, creating a 2‑node cycle.

Example 4

Input:  dependencies = [[]]
Output: False

Explanation: A single resource with no dependencies cannot form a cycle.

Constraints

• n = len(dependencies) is the number of resources, where $0 \le n \le 10^{4}$.
• Each inner list dependencies[i] contains only valid resource indices j such that $0 \le j < n$.
• The total number of dependency entries across all lists is at most $10^{5}$.

Preparation

• Implement a three‑color DFS that visits every component. Test it on a self‑loop, a disconnected cycle, a diamond‑shaped DAG, and an empty graph.
• Re‑derive the O(V + E) time and O(V) space bounds. Be ready to explain why a globally visited node is safe to skip only after it has left the active recursion path.