# 0210. Course Schedule II
###### tags: `Leetcode` `FaceBook` `Medium` `BFS` `DFS` `Graph` `Topological Sort`
Link: https://leetcode.com/problems/course-schedule-ii/
## 思路
### DFS
先建有向图 再做DFS 记得在过程中检测有没有环
### BFS
我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。
## Code
### BFS

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        countPre = [0]*numCourses
        graph = collections.defaultdict(set)
        for a, b in prerequisites:
            countPre[a] += 1
            graph[b].add(a)
        
        ans = []
        queue = []
        for i in range(numCourses):
            if countPre[i]==0:
                queue.append(i)
    
        while queue:
            curr = queue.pop(0)
            ans.append(curr)
            for nextCourse in graph[curr]:
                countPre[nextCourse] -= 1
                if countPre[nextCourse]==0:
                    queue.append(nextCourse)
        
        return ans if len(ans)==numCourses else []

class Solution {
    private List<List<Integer>> edges;
    private int[] edgeNum;
    private int idx = 0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for(int i = 0;i < numCourses;i++){
            edges.add(new ArrayList<Integer>());
        }
        edgeNum = new int[numCourses];
        int[] res = new int[numCourses];
        Arrays.fill(edgeNum,0);
        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
            edgeNum[info[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0;i < numCourses;i++){
            if(edgeNum[i] == 0){
                q.add(i);
            }
        }

        while(!q.isEmpty()){
            int u = q.poll();
            res[idx++] = u;
            for(int v:edges.get(u)){
                edgeNum[v]--;
                if(edgeNum[v] == 0){
                    q.offer(v);
                }
            }
        }

        if(idx != numCourses){
            return new int[0];
        }
        return res;
    }
}

### DFS

class Solution {
    private List<List<Integer>> edges;
    private int[] visited;
    private int[] res;
    private boolean valid = true;
    
    private int idx;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        res = new int[numCourses];
        edges = new ArrayList<List<Integer>>();
        idx = numCourses-1;

        for(int i = 0;i < numCourses;i++){
            edges.add(new ArrayList<Integer>());
        }

        for(int[] info:prerequisites){
            edges.get(info[1]).add(info[0]);
        }

        for(int i = 0;i < numCourses && valid;i++){
            if(visited[i] == 0){
                dfs(i);
            }
        }

        if(!valid){
            return new int[0];
        }
        return res;
    }
    public void dfs(int u){
        visited[u] = 1;
        for(int v:edges.get(u)){
            if(visited[v] == 0){
                dfs(v);
                if(!valid){
                    return;
                }
            }
            else if(visited[v] == 1){
                valid = false;
                return;
            }
        }
        visited[u] = 2;
        res[idx--] = u;
    }
}