class Solution {
    public boolean isCyclic(int V, int[][] edges) {
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<Integer>());
        }
        
        for(int [] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            adj.get(u).add(v);
        }
        
        // to keep a track of nodes if they are visited or not
        boolean[] visited = new boolean[V];
        // to keep a track of nodes if they are visited in same path or not
        boolean[] pathVisited = new boolean[V];
        
        for(int i=0; i<V; i++)
        {
            if(visited[i] == false)
            {
                if(dfs(adj, visited, pathVisited, i))
                    return true;
            }
        }
        return false;
    }
    
    public boolean dfs(ArrayList<ArrayList<Integer>> adj, boolean[] visited, boolean[] pathVisited, int node)
    {
        visited[node] = true;
        pathVisited[node] = true;
        
        // traverse through neighbours
        for(int v : adj.get(node))
        {
            if(visited[v] == false)
            {
                if(dfs(adj, visited, pathVisited, v))
                    return true;
            }
            // if neighbour node is visited already in same path earlier, then it creates a cycle now
            else if(pathVisited[v] == true)
                return true;
        }
        // unmark the current node from pathVisited array because we are going to check another path now
        pathVisited[node] = false;
        return false;
    }
}