Cycle Detection in Task Dependencies

This problem involves determining whether a set of tasks with dependencies forms a cycle. You are given n tasks (numbered from 0 to n-1) and m dependency pairs. Each dependency is of the form \(u\;v\), indicating that task \(u\) must be completed before task \(v\). Your goal is to check if the dependency graph contains any cycle.

A cycle means that there is a path starting and ending at the same task. For example, if task 0 depends on task 1 and task 1 depends on task 0, then these tasks form a cycle. One common strategy to solve this problem is to use Depth-First Search (DFS) with state marking. During DFS, a node can have three states:

• \(0\): unvisited
• \(1\): visiting (currently in the recursion stack)
• \(2\): visited

If you encounter a node that is already in the visiting state, then a cycle exists.

inputFormat

The input is read from stdin and consists of multiple lines. The first line contains an integer (n) indicating the number of tasks. The second line contains an integer (m) representing the number of dependencies. Each of the following (m) lines contains two space-separated integers (u) and (v), indicating that task (u) must be completed before task (v).

outputFormat

Output a single line to stdout that is either 'True' if a cycle exists in the graph, or 'False' if no cycle is found.## sample

4
0

False