###### tags: `Leetcode` `medium` `graph` `topological sort` `dfs` `bfs` `python` `c++`

# 210. Course Schedule II

## [題目連結:] https://leetcode.com/problems/course-schedule-ii/description/

## 題目:
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**.

## 解題想法:
* 相同類型題目詳解: [207. Course Schedule](/txZn8rNCReWvEPygWnh-Zg)

* 題目為，有幾堂課，並且有修課的先後順序，是否能修完所有課，若能修完，回傳任一課堂順序解，否則回傳空array
* numCourses課數
* prerequisites[i] = [ai, bi]
* 必須先修完修bi才能修ai
* 本質為在**有向圖中檢查是否有環**

### **法1: 拓樸排序BFS**
* Step1: 建立有向邊
* ex:[0,1]，表示: 1->0
* Step2: 存所有indegree為0的點
* Step3: while每次選擇indegree為0的點加入最終res，刪掉該點連的所有邊
* 直到找不到-> 存在環
* 若剛好操作n次(n為節點數) -> 無環圖DAG(Directed Acyclic Graph)

## Python: BFS

from collections import defaultdict
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        graph=defaultdict(list)
        indegrees=defaultdict(int)
        #connect the graph
        for v,u in prerequisites:
            graph[u].append(v)
            indegrees[v]+=1
        visited=0 #已拜訪數量
        res=[]
        zeroIndegree=[ node for node in range(numCourses) if indegrees[node]==0]
        while zeroIndegree:
            cur=zeroIndegree.pop()
            visited+=1
            res.append(cur)
            #將鄰居的邊都刪掉
            for neighber in graph[cur]:
                indegrees[neighber]-=1
                if indegrees[neighber]==0:
                    zeroIndegree.append(neighber)
        return res if visited==numCourses else []


numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
result = Solution()
ans = result.findOrder(numCourses,prerequisites)
print(ans)

## C++: BFS

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> graph;
        unordered_map<int,int> indegrees;
        //init
        for (int i=0; i<numCourses; i++) indegrees[i]=0;
        //connect
        for (auto course: prerequisites){
            graph[course[1]].push_back(course[0]);
            indegrees[course[0]]+=1;
        }
        //collect the node which has the zero indegrees
        stack<int> zeroIndegrees;
        for (int i=0; i<numCourses; i++){
            if (indegrees[i]==0)
                zeroIndegrees.push(i);
        }
        int visited=0;
        vector<int> res;
        //bfs
        int curNode;
        while (!zeroIndegrees.empty()){
            curNode=zeroIndegrees.top(); zeroIndegrees.pop();
            visited+=1;
            res.push_back(curNode);
            for (auto neighber: graph[curNode]){
                indegrees[neighber]-=1;
                if (indegrees[neighber]==0)
                    zeroIndegrees.push(neighber);
            }
        }
        if (visited!=numCourses)
            res.clear();
        return res;
    }
};

### 法2: 拓樸排序DFS

* Step1: 建立有向邊
* ex:[0,1]，表示: 1->0

* Step2: 對於每點，設不同狀態進行判別
* 0 = Unknown
* 1 = visiting
* 2 = visited

* Step3: 每次找到新點，判斷此點出發是否有環

* Step4: 子程式bool checkDAG()判斷當前點的拜訪狀態:

## Python: DFS

from collections import defaultdict
class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        graph = defaultdict(list)
        #連邊
        for v,u in prerequisites:
            graph[u].append(v)
        #記錄點的目前狀態 0:尚未拜訪 1:仍在拜訪中 2:已完成拜訪
        visited= [0]*numCourses
        path=[]
        for i in range(numCourses):
            if self.checkDAG(graph,visited,i,path)==False:
                return []  #有環 回傳空array
        return path[::-1]  #因為最先返回的是最深層的
    def checkDAG(self,graph,visited,cur_node,path):
        if visited[cur_node]==1: 
            return False 
        elif visited[cur_node]==2:
            return True
        else:
            visited[cur_node]=1 
            #拜訪鄰居
            for node in graph[cur_node]:
                if self.checkDAG(graph,visited,node,path)==False:
                    return False
            visited[cur_node]=2
            path.append(cur_node)
            return True

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
result = Solution()
ans = result.findOrder(numCourses,prerequisites)
print(ans)

## C++: DFS

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> graph;
        //connect
        for (auto course: prerequisites) graph[course[1]].push_back(course[0]);
        //init
        //0:unknown 1:visiting 2:visited
        vector<int> visited(numCourses,0);
        //dfs
        for (int i=0; i<numCourses; i++){
            if (checkDAG(graph,visited,i)==false)
                return vector<int>();
        }
        reverse(res.begin(), res.end());
        return res;
    }

    bool checkDAG(unordered_map<int,vector<int>>& graph, vector<int>& visited, int curNode){
        if (visited[curNode]==1)
            return false;
        else if (visited[curNode]==2)
            return true;
        else{
            visited[curNode]=1;
            for (int neighber: graph[curNode]){
                if (checkDAG(graph,visited,neighber)==false)
                    return false;
            }
            visited[curNode]=2;
            res.push_back(curNode);
            return true;
        }
    }

private:
    vector<int> res;
};