13 ms Top-sort in C++ with clear explanation


  • 0
    C
    class Solution {
    public:
        vector<int> findOrder(int num, vector<pair<int, int>>& prereq) {
             if (num == 0) return vector<int>();
            // first let's count the in-degree of each point and keep record of the list in its vector
            vector<vector<int>> my(num);     // each course has its own "pointed-to" vertices
            vector<int> inDegree(num, 0);
            vector<int> course; // to record the poped front from the queue
            
            for (auto x : prereq){
                inDegree[x.first]++;
                my[x.second].push_back(x.first);
            }
            // Next we use topological sort to go through the graph
            // we use a queue to put in the courses with 0 in-degree
            // pop each of them and decrease the following courses' in-degree by 1.continue the process
            std::queue<int> topsort;
            for (int i = 0; i< num ; ++i){
                if (inDegree[i] == 0){
                      topsort.push(i);
                }
            }
            while(!topsort.empty()){
                int front = topsort.front();
                course.push_back(front);
                for (auto x : my[front]){    // enter into the adjacent list of the current front point
                    if (--inDegree[x] == 0){
                        topsort.push(x);
                    }
                }
                topsort.pop();
            }
            if (course.size() == num) return course;
            course.clear();
            return course;        
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.