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.

&nbsp;
Example 1:

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.


Example 2:

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.


&nbsp;
Constraints:


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


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
                 
        pre = {} # course: list of prerequisites
        dep = {} # course: list of dependents
        for p in prerequisites:
            if p[0] not in pre:
                pre[p[0]] = set()
            if p[1] not in dep:
                dep[p[1]] = set()
            pre[p[0]].add(p[1])
            dep[p[1]].add(p[0])

        # Kahn's algorithm
        l = []
        s = set()
        for i in range(numCourses):
            if i not in dep: # if no dependents (incoming edge)
                s.add(i) 
        while s:
            n = s.pop()
            l.append(n)
            if n in pre: # if n has prerequisites
                for m in pre[n]: # for each prerequisites m
                    dep[m].remove(n) # remove n from m's dependents list
                    if not dep[m]: # if m has no more dependents
                        s.add(m)
                        
        return len(l) == numCourses
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        boolean [] visited = new boolean[n];
        boolean [] dfsVisited = new boolean[n];
        
        List<List<Integer>> adj = createAdjList(n,prerequisites);
        for(int i=0;i<n;i++){
            if(visited[i]==false){
                if(isCycle(i,adj,visited,dfsVisited)){
                    return false;
                }
            }
        }
        return true;
    }
    //find cycle in a directed graph
    private boolean isCycle(int s,List<List<Integer>> adj,boolean [] visited,boolean[] dfsVisited){
       
        visited[s]=true;
        dfsVisited[s]=true;
            
        for(int v:adj.get(s)){
            if(visited[v]==false){
              if(isCycle(v,adj,visited,dfsVisited)){
                return true;
                }  
            }else if(visited[v]==true && dfsVisited[v]==true) {
                return true;
            }   
        }
        dfsVisited[s]=false;
        return false;
    }
    
    private List<List<Integer>> createAdjList(int n,int[][] prerequisites){
        List<List<Integer>> adj = new ArrayList();
        
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int[] e : prerequisites){
               adj.get(e[1]).add(e[0]);
        }
        return adj;
    }
}
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        map<int, vector<int>>adj;
        vector<int> indegree(numCourses,0);
        vector<int>res;
        for(int i=0;i<prerequisites.size();i++){
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0)
                q.push(i);
        }
        while(!q.empty()){
            int x=q.front();
            q.pop();
            res.push_back(x);
            for(auto u:adj[x]){
                indegree[u]--;
                if(indegree[u]==0){
                    q.push(u);
                }
            }
        }
        return res.size()==numCourses;
        
    }
};
var canFinish = function(numCourses, prerequisites) {
    const adjList = []
    const visit = []
    construAdj()
    for (let i = 0; i < numCourses; i++) {
        if (!dfs(i)) return false
    }
    return true

    function dfs(i) {
        // base case
        if (visit[i]) return false
        if (visit[i] === false) return true

        visit[i] = true

        for (const nei of adjList[i] ?? []) {
            if (!dfs(nei)) return false
        }

        visit[i] = false
        return true
    }

    function construAdj() {
        for (const pre of prerequisites) {
            if (!adjList[pre[0]]) adjList[pre[0]] = []
            adjList[pre[0]].push(pre[1])
        }
    }
};
Course Schedule