Q43 is cycle present in DAG ? GFG (using kahns algo)
Thu Jun 22 2023 09:24:05 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//using kahn's algo
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
ans = new int[V];
idx = 0;
kahn(V , adj);
return idx == V ? false : true;
}
static int ans[];
static int idx ;
public static void kahn(int v, ArrayList<ArrayList<Integer>> graph){
//find indegree
int indegree[] = new int[v];
for(int i = 0 ;i < v ; i++){
for(int edge : graph.get(i)){
indegree[edge] ++;
}
}
//add indegree 0 to q
Queue<Integer> q = new ArrayDeque<>();
for(int i = 0 ;i < v ; i++){
if(indegree[i] == 0)
q.add(i);
}
//DAG no need of visited
//fire BFS
while(q.size() > 0){
int rem = q.remove();
ans[idx] = rem;
idx++;
//reduce indegree of nbrs and add it in the q if 0
//0 means no dependencies they can be printed
for(int edge: graph.get(rem)){
indegree[edge]--;
if(indegree[edge] == 0)
q.add(edge);
}
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1
Comments