Share my C++ solution, easy to understand


  • 0
    V
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            int edges_cnt = prerequisites.size();
            vector<int> ret;
            vector<vector<int>> edges(numCourses, vector<int>(0));//adjacency lists
            vector<int> outdegree(numCourses, 0);
            queue<int> q;
            
            for (int i = 0; i < edges_cnt; i++)
            {
                edges[prerequisites[i].second].push_back(prerequisites[i].first);
                outdegree[prerequisites[i].first]++;
            }
            
            for (int i = 0; i < numCourses; i++)
            {
                if (outdegree[i] == 0)
                    q.push(i);
            }
            
            while (!q.empty())
            {
                int course = q.front();
                q.pop();
                ret.push_back(course);
                
                int n = edges[course].size();
                for (int i = 0; i < n; i++)
                {
                    int tmp = edges[course][i];
                    outdegree[tmp]--;
    
                    if (outdegree[tmp] == 0)
                        q.push(tmp);
                }
            }
            
            if (ret.size() != numCourses)
            {
                vector<int> tmp;
                return tmp;
            }
            
            return ret;
        }
    };
    

Log in to reply
 

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