###### tags: `Leetcode` `medium` `graph` `topological sort` `dfs` `bfs` `python` `c++` `Top 100 Liked Questions`

# 207. Course Schedule

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**.


## 解題想法:
* 同類型題目: [210. Course Schedule II](/p2vAVMAwRdyn_Wb9O7UZpA)
* 題目為，有幾堂課，並且有修課的先後順序，是否能修完所有課
* numCourses課數
* prerequisites[i] = [ai, bi]
* 必須先修完修bi才能修ai
* 本質為在**有向圖中檢查是否有環**

### **法1: 拓樸排序BFS**
* time: O(n^2) space:O(n)
* Step1: 建立有向邊
* ex:[0,1]，表示: 1->0

    for v,u in prerequisites:
        graph[u].append(v) #u指向v
        indegrees[v]+=1  #有人指向v 所以v的indegrees+1

* Step2: 存所有indegree為0的點

    zeroIndegree = [i for i in range(numCourses) if indegrees[i]==0] 
    #不能用 " i for i in indegrees "  
    #Wrong: zeroIndegree = [i for i in indegrees if indegrees[i]==0]
    #因為雖然用defaultdict(int)
    #但是step1建立邊時，indegree只針對非0者進行壘加，所以不知道哪些node indegree為0

* Step3: while每次選擇indegree為0的點，刪掉該點連的所有邊
* 直到找不到-> 存在環
* 若剛好操作n次(n為節點數) -> 無環圖DAG(Directed Acyclic Graph)

    visited = 0 #已經拜訪過的點數量
    #BFS
    while zeroIndegree:
        cur = zeroIndegree.pop()
        visited+=1
        #遍歷所有被cur連到的點
        for node in graph[cur]:
            #將其indegrees-1
            indegrees[node]-=1
            if indegrees[node]==0:
                zeroIndegree.append(node)

## Python: BFS

from collections import defaultdict
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        #graph topological
        graph=defaultdict(list)
        indegrees=defaultdict(int)  #key的默認val為0
        #建立圖
        for v,u in prerequisites:
            #ex: 給[0,1] 表示 1->0
            graph[u].append(v)
            indegrees[v]+=1  
        #存indegrees=0的點
        zeroIndegree = [i for i in range(numCourses) if indegrees[i]==0] 
        visited = 0 #已經拜訪過的點
        #BFS:
        while zeroIndegree:
            cur = zeroIndegree.pop()
            visited+=1
            #遍歷所有被cur連到的點
            for node in graph[cur]:
                #將其in-1
                indegrees[node]-=1
                if indegrees[node]==0:
                    zeroIndegree.append(node)
                    
        return True if visited==numCourses else False
if __name__=='__main__':
    numCourses = 2
    prerequisites = [[1,0]]
    result=Solution()
    ans = result.canFinish(numCourses,prerequisites)
    print(ans)

## C++: BFS

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> graph;
        unordered_map<int, int> indegree;
        for (int i=0; i<numCourses; i++){
            indegree[i]=0;
        }
        //connect the graph
        for (auto course: prerequisites){
            graph[course[1]].push_back(course[0]);
            indegree[course[0]]+=1;
        }
        stack<int> zeroIndegrees;
        //unorder_map: first,second
        //key: course.first
        //val: course.second
        for (auto& course: indegree){ //pointer need &
            if (course.second==0)
                zeroIndegrees.push(course.first);
        }
        int visited=0;
        //bfs
        int curNode;
        while (!zeroIndegrees.empty()){
            curNode=zeroIndegrees.top(); zeroIndegrees.pop();
            visited+=1;
            for (auto neiber: graph[curNode]){
                indegree[neiber]-=1;
                if (indegree[neiber]==0)
                    zeroIndegrees.push(neiber);
            }
        }
        return (visited==numCourses)? true:false;
    }
};

int main(){
    Solution res;
    int numCourse=2;
    vector<vector<int>> prerequsites={
        {1,0},
        {0,1}
    };
    bool ans=res.canFinish(numCourse,prerequsites);
    cout<<ans<<endl; //0 false
    return 0;
}

### 法2: 拓樸排序DFS
* time、space: **皆O(n)**
* Step1: 建立有向邊
* ex:[0,1]，表示: 1->0

    graph = defaultdict(list)
    for v,u in prerequisites:
        graph[u].append(v)

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

    # 0 = Unknown, 1 = visiting, 2 = visited
    visit = [0]*numCourses

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

    for i in range(numCourses):
        if self.checkDAG(graph,visit,i)==False:
            return False
    return True

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

    def checkDAG(self,graph,visit,i):
        if visit[i]==1: #有cycle
            return False
        elif visit[i]==2: #安全
            return True 
        else: #初次拜訪
            visit[i]=1 #將自己狀態改為拜訪中
            #遍歷鄰居
            for node in graph[i]:
                if self.checkDAG(graph,visit,node)==False:
                    return False
            visit[i]=2 #將自己狀態改為已遍歷
            return True

## Python: DFS

from collections import defaultdict
class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        #graph topological 
        #dfs  time space: 皆O(N)
        graph = defaultdict(list)
        for v,u in prerequisites:
            graph[u].append(v)
        # 0 = Unknown, 1 = visiting, 2 = visited
        visit = [0]*numCourses
        for i in range(numCourses):
            if self.checkDAG(graph,visit,i)==False:
                return False
        return True
    
    def checkDAG(self,graph,visit,i):
        if visit[i]==1: #有cycle
            return False
        elif visit[i]==2: #安全
            return True 
        else: #初次拜訪
            visit[i]=1
            #遍歷鄰居
            for node in graph[i]:
                if self.checkDAG(graph,visit,node)==False:
                    return False
            visit[i]=2
            return True
        
if __name__=='__main__':
    numCourses = 2
    prerequisites = [[1,0]]
    result=Solution()
    ans = result.canFinish(numCourses,prerequisites)
    print(ans)

## C++: DFS

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> graph;
        //connect the graph
        for (auto course: prerequisites){
            graph[course[1]].push_back(course[0]);
        }
        //init the visited list
        //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 false;
        }
        return true;
    }

    bool checkDAG(unordered_map<int, vector<int>>& graph, vector<int>& visited, int curPos){
        if (visited[curPos]==1)
            return false;
        else if (visited[curPos]==2)
            return true;
        else{
            visited[curPos]=1;
            //check neighbor of curPos in graph
            for (auto neighbor: graph[curPos]){
                if (checkDAG(graph,visited,neighbor)==false)
                    return false;
            }
            visited[curPos]=2;
            return true;
        }
    }
};

int main(){
    Solution res;
    int numCourse=2;
    vector<vector<int>> prerequsites={
        {1,0},
        {0,1}
    };
    bool ans=res.canFinish(numCourse,prerequsites);
    cout<<ans<<endl; //0 false
    return 0;
}