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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

&nbsp;
Example 1:

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


Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].


Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]


&nbsp;
Constraints:


	1 &lt;= numCourses &lt;= 2000
	0 &lt;= prerequisites.length &lt;= numCourses * (numCourses - 1)
	prerequisites[i].length == 2
	0 &lt;= ai, bi &lt; numCourses
	ai != bi
	All the pairs [ai, bi] are distinct.


class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        d = {i:[] for i in range(numCourses)}
        
        for crs, prereq in prerequisites:
            d[crs].append(prereq)
         
        visit, cycle = set(), set()
        output = []
        def dfs(crs):
            if crs in cycle:
                return False
            if crs in visit:
                return True
            
            cycle.add(crs)
            for nei in d[crs]:
                if not dfs(nei):
                    return False
            cycle.remove(crs)
            visit.add(crs)
            output.append(crs)
            return True
        
        for crs in range(numCourses):
            if not dfs(crs):
                return []
        return output
            
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new HashSet<Integer>());
        }
        
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
            inDegree[pair[0]]++;
        }
        
        // BFS - Kahn's Algorithm - Topological Sort
        Queue<Integer> bfsContainer = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                bfsContainer.add(i);    
            }
        }
        
        int count = 0;
        int[] ans = new int[numCourses];
        while (!bfsContainer.isEmpty()) {
            int curr = bfsContainer.poll();
            ans[count++] = curr;
            for (Integer num : graph.get(curr)) {
                inDegree[num]--;
                if (inDegree[num] == 0) {
                    bfsContainer.add(num);
                }
            }
        }
        
        if (count < numCourses) {
            return new int[] {};
        } else {
            return ans;
        }
    }
}
class Solution {
public:
    vector<int> findOrder(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);
                }
            }
        }
        if(res.size()==numCourses)
            return res;
        return {};

    }
};
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    let visiting = new Set();
    const visited = new Set();
    const adjList = new Map();
    const result = [];
    
	// Generate scaffold of adjacency list
	// initialized with no prereqs
    for (let i = 0; i < numCourses; i++) {
        adjList.set(i, []);
    }
    
	// Fill adjacency list with course prereqs
	// Key is the course
	// Value is any course prereqs
    for (const item of prerequisites) {
        const [course, prereq] = item;
        adjList.get(course).push(prereq);
    }
    
    const dfs = (node) => {
	    // We've already traversed down this path before
		// and determined that it isn't cyclical
        if (visited.has(node)) return true;
		
		// Visiting keeps track of what we've seen
		// during this current traversal and determines
		// if we have a cycle.
        if (visiting.has(node)) return false;
  
		// Mark this node as part of the current traversal
        visiting.add(node);
        
		// Get all adjacent nodes to traverse
		// traverse them in a loop looking for cycles
        const children = adjList.get(node);
        for (const child of children) {
            if (!dfs(child)) return false;
        }
		
		// Ensures we don't re-traverse already traversed nodes since
		// we've already determined they contain no cycles.
        visited.add(node);
		
		// Add this node to the result stack to return at the end
        result.push(node);
        return true;
    }
    
    for (const node of adjList.keys()) {
        if(!dfs(node)) return [];
    }
    
    return result;
};
Course Schedule II