Q43 is Cycle present in DAG ? GFG ( Topological Sort)
Wed Jun 21 2023 20:59:10 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
// Function to detect cycle in a directed graph.
/* we will use topological sort for this , we will keep 2 boolean array visited and
recursion_stack
if a cycle is present it will come in the recursion_stack , as its a DAG
Algo
1) fire topological sort from all vertice
2) if from any vertice you find an already visited vertex in the same recursion , there is a cycle
*/
public boolean isCyclic(int v, ArrayList<ArrayList<Integer>> graph) {
boolean visited[] = new boolean[v];
boolean recursion_stack[] = new boolean[v];
for(int i = 0 ; i< v; i++){
if(visited[i] == false){
if(topo(graph,visited , recursion_stack , i))
return true;
}
}
return false;
}
public boolean topo(ArrayList<ArrayList<Integer>> graph , boolean visited[],boolean recursion_stack[] , int src){
//if same vertex is coming again in the same recursion stack , there is a cycle
if(recursion_stack[src] == true)
return true;
//an already visited vertex can come
if(visited[src] == true)
return false;
//marking vertex as visited in visited[] and current recursion_stack[]
visited[src] = true;
recursion_stack[src] = true;
//adding neighours
for(int edge : graph.get(src)){
if(topo(graph , visited , recursion_stack , edge))
return true;
}
//removing src from current recursion_stack while backtracking
recursion_stack[src] = false;
return false;
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1
Comments