Detect Cycle in a Directed Graph

Detect Cycle in a Directed Graph

Determine whether a directed graph contains a cycle using DFS and a recursion stack.

Input format

The first line contains N and M. The next M lines contain directed edge pairs (u → v).

Output format

Print true if the graph contains a cycle, false otherwise.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

16 18
9 10
11 0
13 8
12 8
7 0
1 6
8 2
6 1
8 7
7 12
7 8
4 11
7 9
5 7
4 0
1 15
7 6
5 15

true

6 13
1 4
5 2
1 5
5 4
2 1
2 5
2 4
1 3
3 2
1 2
0 5
0 4
3 5

true