# 【LeetCode】 207. Course Schedule

## Description
> There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses-1`.
> Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: `[0,1]`
> Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

> Constraints:
> * The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
> * You may assume that there are no duplicate edges in the input prerequisites.
> * `1 <= numCourses <= 10^5`

> 你選了總共`numCourses`堂的課程，將它們標記為 `0` 到 `numCourses-1`。
> 有些課程有擋修，例如你需要先修課程 1 才能修課程 0 ，這被表示成一個對子：`[0,1]`
> 給予課程的總數和一個擋修表，判斷是否可能完成所有課程。

> 限制：
> * 輸入的擋修表使用邊的列表(list of edges)表示法，而不是鄰近矩陣(adjacency matrices)，查閱更多圖的表示法來得到更多相關知識。
> * 你可以假設擋修表不會有重複的邊。
> * `1 <= numCourses <= 10^5`

## Example:

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.

## Solution

* 先提一下，很久沒寫graph相關的東西，有些生疏，code應該可以精簡很多(我的執行時間很醜)。
* 這一題可以把擋修關係畫成有向圖，然後只要檢查圖是否有cycle就是答案。
* 對於graph不熟或是還沒學過的朋友，可以去看我的[資料結構筆記](https://hackmd.io/@Zero871015/DSNote)`16、17`章喔~
* 檢查cycle的方式，我這邊是從每個點去跑DFS，如果過程中跑回自己就代表有cycle。
* 感覺好像在這個部分會有跑重複的部分，但我不知道怎麼改寫演算法。

### Code

class Solution {
public:
    bool getSelf(int now, int vertex, vector<bool>& touched)
    {
        touched[now] = true;
        
        for(auto next : graph[now])
        {
            if(next == vertex)
                return true;
            if(touched[next] == false)
            {
                if(getSelf(next, vertex, touched))
                    return true;
            }
        }
        return false;
    }
    
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        /* Build graph */
        graph = vector<vector<int>>(numCourses);
        for(int i = 0; i < prerequisites.size(); i++)
            graph[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        /* Check the graph has a circle or not */
        /* Check each vertex can get itself or not */
        for(int i = 0; i < numCourses; i++)
        {
            vector<bool> touched(numCourses, false);
            if(getSelf(i, i, touched) == true)
                return false;
        }
        return true;
    }
private:
    vector<vector<int>> graph;
};

###### tags: `LeetCode` `C++`