【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不熟或是還沒學過的朋友，可以去看我的資料結構筆記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++