Detect Cycle in Directed Graph

# Detect Cycle in Directed Graph ## Difficulty Medium ## Tags `graph`, `dfs`, `topological sort` ## Problem Statement Given a directed graph represented as an adjacency list, determine if the graph contains any cycles. A cycle exists if you can start at a node and return to it by following the directed edges. ## Constraints - The graph may have disconnected components. - Nodes can be integers or strings. - 1 ≤ number of nodes ≤ 10⁴ - The graph may contain self-loops. ## Signatures ### Python ```python def has_cycle(graph: Dict[T) -> bool: pass ``` ### Java ```java public class Solution { public boolean has_cycle(Object graph) { return null; } } ``` ### Csharp ```csharp public class Solution { public bool has_cycle(Object graph) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: bool has_cycle(Object graph) { } }; ``` ### C ```c bool has_cycle(Object graph) { } ``` ### Ruby ```ruby def has_cycle(graph) end ``` ### Perl ```perl sub has_cycle { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def has_cycle(graph: Object): Boolean = { } } ``` ### Haskell ```haskell has_cycle :: ... -> ... has_cycle args = undefined ``` ### Clojure ```clojure (defn has_cycle [graph] ) ``` ### Scheme ```scheme (define (has_cycle graph) ) ``` ## Examples ### Example 1 **Input:** ``` graph = {0: [1], 1: [2], 2: [0]} ``` **Output:** ``` True ``` **Explanation:** 0 → 1 → 2 → 0 forms a cycle. ### Example 2 **Input:** ``` graph = {0: [1, 2], 1: [2], 2: []} ``` **Output:** ``` False ``` **Explanation:** No path leads back to a previously visited node in the current path. ### Example 3 **Input:** ``` graph = {0: [1], 1: [2], 2: [3], 3: [1]} ``` **Output:** ``` True ``` **Explanation:** 1 → 2 → 3 → 1 forms a cycle. ### Example 4 **Input:** ``` graph = {"a": ["b"], "b": ["c"], "c": [], "d": ["a"]} ``` **Output:** ``` False ``` **Explanation:** No cycles exist in this DAG. ## Hints 1. Use DFS with three states for each node: UNVISITED, VISITING, VISITED. 2. VISITING means the node is in the current recursion stack. 3. If you encounter a node that is VISITING, a cycle exists. 4. Mark nodes as VISITED when all their descendants have been processed.