192. Detect a cycle in a directed graph
Given a directed graph with V vertices labeled from 0 to V-1. The graph is represented using an adjacency list where adj[i] lists all nodes connected to node. Determine if the graph contains any cycles.
Example 1:
Input: V = 6, adj= [ [1], [2, 5], [3], [4], [1], [ ] ]
Output: True
Explanation: The graph contains a cycle: 1 -> 2 -> 3 -> 4 -> 1.
Example 2:
Input: V = 4, adj= [[1,2], [2], [], [0,2]]
Output: False
Explanation: The graph does not contain a cycle.
Now Your Turn!
Pick the correct output for the given inputInput: V = 3, adj= [[1], [2], [0]]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= V <= 10^4
- adj.size() == V
- 0 <= adj[i][j] < V
- 1 <= sum(adj[i].size()) <= 104