# Leetcode 207: Course Schedule (已解決)

參考到一篇，先用indegree來找出需先上完的課，來當作第一點，在用queue遍尋的同時，將已走訪的點設為"-1"，若等於0則代表是新的點還需要再丟回去queue裡，如果成功遍尋完，就回傳true

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        //to decide which node is first node
        vector<int> indegrees(numCourses,0);
        for(int i=0;i<prerequisites.size();++i){
            indegrees[prerequisites[i][1]]++;
        }
        
        //build a adjacency list
        map<int, vector<int>>adj;
        for(int i=0;i<prerequisites.size();i++){
            adj[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }

        //push first node to queue
        queue<int>q;
        for(int i=0;i<indegrees.size();i++){
            if(indegrees[i]==0)
                q.push(i);
        }

        //Traversal
        for(int i=0;i<numCourses;i++){

            if(q.empty())
                return false;

            int tmp = q.front();
            q.pop();

            //to record the checked nodes
            indegrees[tmp]=-1;

            for(auto it : adj[tmp]){
                indegrees[it]--;
                if(indegrees[it]==0){
                    q.push(it);
                }
            }
        }
        return true;
    }
};

# result :

Runtime
50 ms

Beats
45.10%
    
Memory
14.3 MB

Beats
37.27%