Cycle In Directed Graph
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/
* ============================================================================================
* PROBLEM: Cycle in Directed Graph
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given a directed graph with A nodes and M edges.
* Determine if the graph contains at least one directed cycle.
* - A cycle must contain at least two nodes.
* - The graph may be disconnected.
* - Return 1 if a cycle exists, else 0.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* In a directed graph, a cycle exists if and only if there is a Back-Edge.
* A back-edge is an edge from a node to one of its ancestors in the DFS tree.
*
* Algorithm (DFS with Recursion Stack):
* 1. Build an adjacency list.
* 2. Maintain two boolean arrays:
* - visited[]: Tracks nodes that have been fully processed.
* - pathVisited[]: Tracks nodes currently in the active recursion stack.
* 3. Iterate through all nodes (1 to A) to handle disconnected components:
* If node is not visited, call DFS(node).
*
* DFS(u):
* - Mark visited[u] = true and pathVisited[u] = true.
* - For each neighbor v of u:
* - If pathVisited[v] is true:
* - We found a back-edge to an active ancestor. Cycle Detected. Return 1.
* - Else if visited[v] is false:
* - Recursively call DFS(v). If it returns 1, propagate it.
* - Backtrack*: Mark pathVisited[u] = false before returning (removing from stack).
*
* Alternative (Kahn's Algorithm):
* If we perform a Topological Sort and the number of nodes in the sorted list
* is less than A, a cycle exists.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Time Complexity: O(A + M)
* Space Complexity: O(A + M) - Adjacency list + recursion stack.
*
* ============================================================================================
/
public class CycleInDirectedGraph {
public int solve(int A, int[][] edges3) {
// TODO: Implement solution
return 0;
}
}