cycleDetectionInDirectedGraph.java

importjava.util.ArrayList;


// check whether the graph is DAG, directed acyclic(without cycles) graph
publicclasscycleDetectionInDirectedGraph {
privatebooleancheckCycle(intnode, ArrayList<ArrayList<Integer>> adj, int[] visited, intdfsVisited[]) {
visited[node] = 1;
dfsVisited[node] = 1;
for (Integerchild : adj.get(node)) {
if (visited[child] == 0) {
if (checkCycle(child, adj, visited, dfsVisited))
returntrue;
 } elseif (dfsVisited[child] == 1)
returntrue;
 }
returnfalse;
 }

publicbooleanisCyclic(intN, ArrayList<ArrayList<Integer>> adjlist, intn) {
intvisited[] = newint[N];
intdfsVisited[] = newint[N];
for (inti = 0; i < n; i++) {
if (visited[i] == 0) {
if (checkCycle(i, adjlist, visited, dfsVisited) == true) {
returntrue;
 }
 }
 }
returnfalse;
 }
}