Cycle Detection directed graphs

 import java.util.*;

public class CycleDetectionDirected {
    static class Edge{
        int src;
        int dest;
        public Edge(int s,int d){
            this.src=s;
            this.dest=d;
        }
    }
    /*
     *
     *    0---->2
     *    | \   |
     *    |   \ |
     *    1---->3
     */
    public static void Create(ArrayList<Edge>[]graph){
        for(int i=0;i<graph.length;i++){
            graph[i]=new ArrayList<>();
        }
        graph[0].add(new Edge(0, 2));
        graph[1].add(new Edge(1, 0));
        graph[2].add(new Edge(2, 3));
        graph[3].add(new Edge(3, 0));
    }
    public static boolean isCycleUtil(ArrayList<Edge>graph[],int curr,boolean vis[],boolean stack[]){
        vis[curr]=true;
        stack[curr]=true;
        for(int i=0;i<graph[curr].size();i++){
            Edge e=graph[curr].get(i);
            if (stack[e.dest]) {
                return true;
            }
            if (!vis[e.dest] && isCycleUtil(graph, e.dest, vis, stack)) {
                return true;
            }
        }
        stack[curr]=false;
        return false;
    }

    public static boolean isCycle(ArrayList<Edge>graph[]){
        boolean vis[]=new boolean[graph.length];
        boolean stack[]=new boolean[graph.length];
        for(int i=0;i<graph.length;i++){
            if (!vis[i]) {
                if (isCycleUtil(graph,i,vis,stack)) {
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int v=4;
        ArrayList<Edge>graph[]=new ArrayList[v];
        Create(graph);
        System.out.println(isCycle(graph));
    }
}

Comments