Algorithms and Data Structures

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.
notion image
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:
  1. Vertex is not visited
  1. Vertex and its DFS subtree are being processed
  1. 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:
  1. Mark all the vertices as not visited
  1. Start a DFS from some vertex
  1. For the current vertex, mark it as being processed
  1. 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
  1. v=3, p=-1 → color = [1, 1, 1, 2] ⇒ explore all the neighbors of 3 ⇒ [2]
  1. v=2, p=3 → color = [1, 1, 2, 2] ⇒ explore all the neighbors of 2 ⇒ [0, 1]
  1. v=0, p=2 → color = [2, 1, 2, 2] ⇒ explore all the neighbors of 0 ⇒ [1, 2]
  1. 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 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in