# 207. Course Schedule
#### Difficulty: Medium
link: https://leetcode.com/problems/course-schedule/

整個問題能被建成一個graph，每一堂課程都是node，先修關係當作edge，這題相當於在檢查整個graph是不是DAG，有沒有cycle存在。

DFS和BFS的做法都行。

### 1. DFS
#### $O(V+E)$ runtime, $O(V+E)$ space

用DFS判斷有沒有cycle，需要至少兩種node的狀態：已拜訪和正在拜訪。如果下一個要拜訪的node，恰好是正在拜訪的node，就代表有cycle。

##### python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # build the adjacence list
        graph = [[] for _ in range(numCourses)]
        for v, u in prerequisites:
            graph[u].append(v)
        
        # visit node
        visited = [0 for _ in range(numCourses)]
        def dfs(node):
            if visited[node] == 1: # the node has been visited
                return True
            elif visited[node] == -1: # the node is being visited
                return False
            
            # the node has not been visited
            visited[node] = -1
            for neigh in graph[node]:
                if not dfs(neigh):
                    return False
            visited[node] = 1
            return True
        
        for i in range(numCourses):
            if not dfs(i):
                return False
        
        return True

### 2. BFS
#### $O(1)$ runtime, $O(1)$ space

先從不需要必修的課程開始，每修完一堂課，再去檢查是否解鎖新的課程。最後，看看是不是修完了所有的課，如果修不完就代表有cycle。

##### python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # build the adjacence list and calculate indegree
        indegree = [0] * numCourses
        graph = [[] for _ in range(numCourses)]
        for v, u in prerequisites:
            graph[u].append(v)
            indegree[v] += 1
        
        # start from courses which have no prerequisites
        queue = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        
        visited = 0
        while queue:
            node = queue.popleft()
            visited += 1
            for neigh in graph[node]:
                indegree[neigh] -= 1
                if indegree[neigh] == 0:
                    queue.append(neigh)
        
        return visited == numCourses

###### tags: `leetcode`