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.
Example 1
Input
nodes (int) =
3edges (int[][]) =
[[0,1],[1,2],[2,0]]size (int) =
3Returns (boolean)
trueExample 2
Input
nodes (int) =
3edges (int[][]) =
[[0,1],[1,2]]size (int) =
2Returns (boolean)
falseExample 3
Input
nodes (int) =
1edges (int[][]) =
[]size (int) =
0Returns (boolean)
falseUse 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 falseReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run