# 207. Course Schedule

###### tags: `leetcode` `DFS` `207` `medium`

## :memo: Question
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`.

### Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

### Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

* `1 <= numCourses <= 105`
* `0 <= prerequisites.length <= 5000`
* `prerequisites[i].length == 2`
* `0 <= ai, bi < numCourses`
* `All the pairs prerequisites[i] are unique.`

## :memo: 題意
:bulb: 題目就是要讓你判斷是否為有向無環圖

## :memo: leetcode solution
* :medal: **思考一**: 將關係圖拉出來，這是有向圖，請注意關西圖要怎麼生成
* :medal: **思考二**: dfs 不j4
* :medal: **思考三**: 這邊有個點當你將這個點走完後要給他一個記號說明，這個點已經被檢查過了，跟他相關的點也沒有問題不會造成一個迴圈。跟已經看過的記號要區別。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        relation = [[] for i in range(numCourses)]
        
        for a,b in prerequisites:
            relation[a].append(b)
        
        seen = [0 for i in range(numCourses)]
        
        def dfs(i, seen):
            
            if seen[i] == 1: return False
            if seen[i] == 2: return True
            
            seen[i] = 1
            
            for j in relation[i]:
                if not dfs(j, seen):
                    return False
            
            seen[i] = 2
            
            return True
        
        
        for i in range(numCourses): 
            if not dfs(i, seen):
                return False
                    
        return True

## :memo: bigO
* 時間複雜度: e (build relation matrix) + v (dfs 有多少點就會走多少個)
* 空間複雜度: 2 * v ( relation matrix + seen matrix)

## :-1: **檢討**
* 有向無環圖與無向無還圖的relation table 建立不一樣。
* 如何表示且建立 relation talbe，可以看以下連結中的表示法(representation)
* http://alrightchiu.github.io/SecondRound/graph-introjian-jie.html