C++, base on an in-degree array


  • 1
    S
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int>> matrix(numCourses, vector<int>());
            for(auto itr = prerequisites.begin(); itr != prerequisites.end(); itr++){
                matrix[itr->second].push_back(itr->first);
            }
            
            vector<int> d(numCourses, 0);
            for(int i = 0; i < numCourses; i++){
                for(auto itr = matrix[i].begin(); itr != matrix[i].end(); itr++){
                    d[*itr]++;
                }
            }
            
            vector<int> topoList;
            for(int j = 0; j < numCourses; j++){
                int i;
                for(i = 0; i < numCourses && d[i] != 0; i++);
                if(i == numCourses) return vector<int>();
                topoList.push_back(i);
                d[i] = -1;
                for(auto itr = matrix[i].begin(); itr != matrix[i].end(); itr++){
                    d[*itr]--;
                }
            }
            return topoList;
        }
    };

Log in to reply
 

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