# Detecting Cycles in a Graph

Detecting cycles in graphs is essential for understanding the structure and properties of data across various domains, such as dependency management, deadlock detection, and network routing. By identifying cycles, we can prevent issues like circular dependencies, inefficiencies, and even system failures.

A modified version of DFS can be used to detect a cycle in a graph.

When traversing a graph with DFS we usually mark vertices as visited/used or not visited. When detecting cycles, thatβs not enough. We need to keep 3 states for each vertex:

- Vertex is not visited

- Vertex and its DFS subtree are being processed

- Vertex is fully visited (with all the child nodes)

This way we can detect a cycle if we reach a vertex that is currently being processed by traversing the graph.

β°

If we reach a vertex that is marked as being processed (2) while traversing the graph, then we have found a cycle.

The algorithm would perform the following steps:

- Mark all the vertices as not visited

- Start a DFS from some vertex

- For the current vertex, mark it as being processed

- When all the child nodes of the current vertex have been processed, mark it as fully visited

The algorithm can be applied to both directed and undirected graphs:

```
color = [1] * n # color of vertices (1: not visited, 2: being processed, 3: fully visited)
def dfs(v, p): # depth-first search (v: vertex, p: parent)
color[v] = 2 # mark vertex as being processed
cycle = False # flag to check if there is a cycle
for to in g[v]: # for each vertex connected to v
if color[to] == 1: # if vertex is not visited
cycle |= dfs(to, v) # call dfs on vertex and mark if there is a cycle
elif color[to] == 2 and to != p: # if vertex is being processed and it is not the parent
cycle = True # mark flag as True
color[v] = 3 # mark vertex as fully visited
return cycle # return flag
for start in range(n): # for each vertex
if color[start] == 1: # if vertex is not visited
if dfs(start, -1): # call dfs on vertex and check if there is a cycle
print('Cycle') # print cycle
break # break loop
else: # If the loop wasn't stopped with break
print('No cycle') # print no cycle
```

Note that for directed graphs, taking into account the parent vertex is not necessary. Can you tell why π€?

Β

Letβs simulate the algorithm on several inputs:

## n = 4, e = 4

The input

`a, b`

pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]The starting vertex is 3

`v=3, p=-1`

β`color = [1, 1, 1, 2]`

β explore all the neighbors of 3 β`[2]`

`v=2, p=3`

β`color = [1, 1, 2, 2]`

β explore all the neighbors of 2 β`[0, 1]`

`v=0, p=2`

β`color = [2, 1, 2, 2]`

β explore all the neighbors of 0 β`[1, 2]`

`v=1, p=0`

β`color = [2, 2, 2, 2]`

β explore all the neighbors of 1 β`[0, 2]`

β 0 is marked as 1 β mark`cycle = True`

β`return True`

Challenge: Check if a graph contains a cycle

Given a directed graph with

`v`

vertices and `e`

edges, you are asked to check if the graph contains a cycle. Input

The first line of the input contains two integers

`v`

(1 β€ v β€ 100 000) and `e`

(1 β€ e β€ 100 000).The following

`e`

lines contain pairs of integers `v1`

, `v2`

(1 β€ v1, v2 β€ v) which means that there is a path from vertex `v1`

to the vertex `v2`

. Output

The program should print

`Yes`

if the graph has a cycle and `No`

otherwise. Examples

Input | Output |

4 3
1 2
2 3
3 1
| Yes |

4 3
1 2
1 3
2 4 | No |

Β

#### Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB