There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

We can also use a depth-first search (DFS) traversal to detect a cycle in a directed graph.

In DFS, we use a recursive function to explore nodes as far as possible along each branch. Upon reaching the end of a branch, we backtrack to the previous node and continue exploring the next branches.

Once we encounter an unvisited node, we will take one of its neighbor nodes (if exists) as the next node on this branch. Recursively call the function to take the next node as the 'starting node' and solve the subproblem.

A node remains in the DFS recursion stack until all of its branches (all nodes in its subtree) have been explored. When we have examined all of a node's branches, i.e. visited all of the nodes in its subtree, the node is removed from the DFS recursive stack.

• We create an adjacency list adj in which adj[x] contains all the nodes with an incoming edge from node x, i.e., neighbors of node x. We create this adjacency list by iterating over prerequisites. For every prerequisite in prerequisites, we add an edge from prerequisite[1] to prerequisite[0].
• Create two boolean arrays, visit and inStack, each of size n. The visit array keeps track of visited nodes and inStack keeps track of nodes that are currently in the ongoing DFS stack. It will help us to detect a cycle in the graph.
• For each node we begin a DFS traversal. We implement the dfs method which takes four parameters: an integer node from which the current traversal begins, adj, visit, and inStack. It returns a boolean indicating whether there is a cycle in the graph. If any dfs call returns true, we have a cycle. In such a case, we return false immediately as our answer to the problem. Otherwise, if no dfs call from all the nodes result in a cycle, we return true. We perform the following in this method:
• If node is already present in inStack, we have a cycle. We return true.
• If node is already visited, we return false because we already visited this node and didn't find a cycle earlier.
• We mark node as visited and also set inStack[node] = true.
• We iterate over all the outgoing edges of node and for each neighbor, we recursively call dfs(neighbor, adj, visit, inStack). If we get a cycle from neighbor, we return true.
• After we have processed all the outgoing edges of node, we mark inStack[node] = false to mark node as out of stack. We also return false as we didn't find any cycle.

class Solution {
    // Map each course to its prerequisites
    private Map<Integer, List<Integer>> preMap = new HashMap<>();
    // Store all courses along the current DFS path
    private Set<Integer> visiting = new HashSet<>();

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for(int i=0;i<numCourses;i++){
            preMap.put(i,new ArrayList<>());
        }
        for(int[] prereq : prerequisites){
            preMap.get(prereq[0]).add(prereq[1]);
        }
        for(int c=0;c<numCourses;c++){
            if(!dfs(c)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int crs){
        if(visiting.contains(crs)){ return false;}
        if(preMap.get(crs).isEmpty()) return true;

        visiting.add(crs);
        for(int pre:preMap.get(crs)){
            if(!dfs(pre)) {return false;}
        }
        visiting.remove(crs);
        preMap.put(crs,new ArrayList<>());
        return true;
    }
}

Here, n be the number of courses and m be the size of prerequisites.

Time complexity: O(m+n)

Space Complexity : O(m+n)