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;
    }