210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

Solution:
Need to build up the directed graph first. Then apply BSF strategy. Start with the zero-indegree (means no prerequisite is needed) elements, and gradually decease the indegrees of the elements that can now be partially accessed. Once the indegree becomes zero, it means it can be fully accessed. If all the elements can be accessed, the total number of them should be the total number of the courses. Or there should be cycle existed. And it is impossible to finish all the courses. Then return empty vector.
(update: the visit vector is not necessary, since inD has enough constrain to avoid duplicates.)

Code:

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> res, inD(numCourses, 0);
        vector<vector<int>> graph(numCourses, vector<int>(0));
        for(auto a:prerequisites){//build graph and indegrees;
            graph[a.second].push_back(a.first);
            ++inD[a.first];
        }
        vector<bool> visit(numCourses, true);
        queue<int> q;
        for(int i=0; i<numCourses; ++i){
            if(!inD[i]){
                q.push(i);
                res.push_back(i);
            } 
        }
        while(q.size()){
            int t = q.front();
            q.pop();
            for(auto a:graph[t]){
                if(visit[a] && inD[a] == 1){
                    res.push_back(a);
                    visit[a] = false;
                }
                --inD[a];
                if(!inD[a]) q.push(a);
            }
        }
        if(res.size()!=numCourses) res.clear();
        return res;
    }
}; 

http://dongxicheng.org/structure/trietree/