Detect Cycle in a Directed Graph

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
62 upvotes
Asked in companies
AmazonAmerican ExpressOYO

Problem statement

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer T, the number of test cases.

The first line of each test case contains two single space-separated integers ‘V’, and ‘E’. ‘V’ represents the number of nodes and ‘E’ represents the number of edges in the graph.

From the second line onwards of each test case, the next 'E' lines will denote the edges of the graph where every edge is defined by two single space-separated integers 'A' and 'B', which signifies an edge from vertex 'A’ to vertex 'B'.
Output Format: 
For each test case print "true" if a cycle exists, else "false".
Constraints: 
1 <= T <= 10
1 <= V <= 10^3
0 <= E <= 10^3
0 <= A, B < V

Time Limit: 1 sec
Sample Input 1:.
2
4 4
0 1
1 2
2 3
3 0
3 3
1 0
1 2
0 2
Sample Output 1:
true
false
Explanation for Sample Input 1:
In the first case,
From node 0 we can reach 0 again by following this sequence of nodes in the path: 0,1,2,3,0. As we can see in the image below.

Example

In the second case,
There is no cycle in the given graph. As we can see in the image below.

Example

Sample Input 2:
2
3 2
0 1
0 2
3 3
1 1
0 2
1 2
Sample Output 2:
false
true
Hint

Can you think of changing the directed tree to a cyclic directed graph by adding one edge?

Approaches (1)
Using DFS

To change a directed tree to a cyclic directed graph by adding one edge, we can choose a node that has more than zero ancestors and add an edge from that node to one of its ancestors. This can always form a complete cycle. This edge is called the back edge.
 

The basic idea is to traverse a graph using DFS and keep track of visited nodes and search for the back edge. If we found any back edge, we will return true, else we will return false.
 

DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (self-loop) or one of its ancestors in the tree produced by DFS.

 

To detect a back edge, we can use coloring to keep track of visited nodes as well as ancestors. The color “0” represents an unvisited node. All the nodes with the color “1” represent the ancestor of the node. The color “2” represents visited nodes that are not ancestors of the node. We can traverse the graph using DFS and for each node, we check if there is any back edge that connects to its ancestor with color “1”. If we find any back edge then return true otherwise return false.

 

For a disconnected graph, we run the same algorithm of each connected graph and return true if there is a back edge in any of the connected graphs.
 

Algorithm:

 

  • Insert all the edges in the graph and make an adjacency list “graph”.
  • Initialize an array “color” with all the values “0” representing unvisited nodes.
  • Iterate over the nodes and for each unvisited node with color “0”: traverse the graph using DFS. If DFS returns true then there is a back edge in the graph. So return true.
    • Consider the recursive function “DFS” that takes three arguments, “U” represents the node number, “color” represents the color of the nodes, “graph” represents the adjacency list.
    • In DFS, first color the node “U” with 1, which represents the node “U” will be the ancestor of the future nodes.
    • Iterate over all adjacent nodes “V”:
      • If the color of node “V” is 1, that means “V” is the ancestor of “U”, that also means the edge from “U” to “V” is the back edge which forms a cycle. So return true.
      • If the color of node “V” is 0, make a recursive call on node “V” to check for a back edge in the subtree of  “V”. if there is a back edge then return true.
    • If there we can not find the back edge, return false.
  • Otherwise, return false.
Time Complexity

O(V + E), Where ‘V’ is the number of nodes and E represents the number of edges in the given graph.

 

Since we are visiting each node and edge of the given graph only once. Therefore time complexity will be O(V + E).

Space Complexity

O(V + E), Where ‘V’ is the number of nodes and E represents the number of edges in the given graph.


Since we are constructing an adjacency list and storing the color of each node in an array of size “N”. So the overall space complexity will be O(V + E).

Code Solution
(100% EXP penalty)
Detect Cycle in a Directed Graph
Full screen
Console