28 lines of C++


  • 0
    S
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int> > matrix(numCourses);
            vector<int> indegree(numCourses);
            
            for (auto it: prerequisites) {
                matrix[it.second].push_back(it.first);
                indegree[it.first]++;
            }
            
            queue<int> q;
            // initialize queue
            for (int i = 0; i<numCourses; ++i) {
                if (indegree[i] == 0)
                    q.push(i);
            }
            vector<int> res;
            while(!q.empty()) {
                int curr = q.front(); q.pop();
                res.push_back(curr);
                for(auto it: matrix[curr]) {
                    if(--indegree[it] == 0) 
                        q.push(it);
                }
            }
            if (res.size() != numCourses) {
                res.clear();
            }
            return res;
        }
    

  • 0
    C

    no need to check cycle, nice!


Log in to reply
 

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