Intermediate Level
Implement the detectCycleDirectedGraph method that checks whether a directed graph contains a cycle.
The input contains the number of graph nodes and a list of directed edges.
Your task is to check whether the directed graph contains a cycle. A cycle exists when you can start from a node, follow directed edges, and reach the same node again.
For example, edges 0 -> 1, 1 -> 2, and 2 -> 0 form a cycle.
Use depth-first search with three visit states.
Mark a node as visiting when it is currently in the recursion path. If DFS reaches a node that is already marked as visiting, a cycle has been found. After all outgoing edges of a node are processed, mark it as visited.
Run DFS from every unvisited node because the graph may have disconnected parts.
Pseudocode:
function detectCycleDirectedGraph(nodes, edges, size):
graph = adjacency list for nodes
for each edge in edges:
add edge[1] to graph[edge[0]]
state = array filled with 0
// 0 = unvisited, 1 = visiting, 2 = visited
for node from 0 to nodes - 1:
if state[node] == 0 and hasCycle(node):
return true
return false
function hasCycle(node):
state[node] = 1
for each nextNode in graph[node]:
if state[nextNode] == 1:
return true
if state[nextNode] == 0 and hasCycle(nextNode):
return true
state[node] = 2
return false