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

此題相當於找出一組topological sort，同樣有DFS和BFS兩種做法。

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

DFS的做法來找topological sort，按照拜訪的結束時間由晚到早排序。

##### python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # build the adjacence list
        graph = [[] for _ in range(numCourses)]
        for v, u in prerequisites:
            graph[u].append(v)
        
        # topological sorted order
        ans = []
        
        # 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
            ans.append(node)
            return True
        
        for i in range(numCourses):
            if not dfs(i):
                return []
        
        return reversed(ans)

### 2. BFS (Kahn's algorithm)
#### $O(V+E)$ runtime, $O(V+E)$ space

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

##### python

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 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
        course_order = []
        while queue:
            node = queue.popleft()
            visited += 1
            course_order.append(node)
            for neigh in graph[node]:
                indegree[neigh] -= 1
                if indegree[neigh] == 0:
                    queue.append(neigh)
        
        if visited == numCourses:
            return course_order
        else:
            return []

###### tags: `leetcode`