Prerequisites: Graphs, DFS
Problem: Implement the algorithm to check if a given directed graph contains any cycle.
Solution Approach: As mentioned on the problem statement page, we run a series of DFS to find the cycle in a directed graph.
Key Idea: The algorithm uses a coloring scheme to mark the state of each node during the DFS traversal. Three possible colors are used:
White (0): Unvisited node.
Gray (1): Node is currently in the process of being visited.
Black (2): Node has been visited and processed.
DFS Traversal:
For each unvisited node in the graph, initiate a DFS traversal. During the DFS, mark the current node as gray (color[node] = 1) when starting the exploration. Recursively visit each neighbor of the current node. If a neighbor is already marked as gray, a cycle is detected. If the DFS traversal completes without finding a cycle, mark the current node as black (color[node] = 2).
Cycle Detection:
A cycle is detected when a node currently being visited (gray) is encountered during the DFS traversal. This indicates that there is a back edge in the graph, forming a cycle.
Time complexity: O(N + M) as we need to explore all nodes using DFS.
Space complexity: O(N) as we need to store the colors of the nodes in an array.