# Leetcode 210: Course Schedule II (已解決)

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        
        map<int, vector<int>> adj; 
        vector<int> rec(numCourses,0); //紀錄表
        queue<int> bfs;
        vector<int> ans;

        //製作adj
        for(auto it : prerequisites){
            adj[it[1]].push_back(it[0]);
            rec[it[0]]++;//找出哪點，可能是起點
        }

        //將起點加入bfs
        for(int i=0;i<rec.size();i++){
            if(rec[i]==0)
                bfs.push(i);
        }
        
        
        while(!bfs.empty()){
            int tmp = bfs.front();
            bfs.pop();
            ans.push_back(tmp);
            
            for(auto it : adj[tmp]){
                rec[it]--;
                if(rec[it]==0){
                    bfs.push(it);
                }
            }
        }

        if(ans.size()==numCourses)
            return ans;
        else
            return {};
        
    }
};