20 lines no search simple c++ solution


  • 0
    F

    The idea is simple,

    1. Find courses with 0 in dependency, if not found return error
    2. Add them to the result list
    3. Remove them from graph
    4. Go to 1 until all courses added to result list
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            //build graph
            vector<pair<int, list<int>>> g(numCourses);
            for (auto e : prerequisites) {
                g[e.second].second.push_back(e.first);
                g[e.first].first++;
            }
            vector<int> res;
            while(res.size() < numCourses) {
                int start = res.size();
                for (int n = 0; n < g.size(); n++) {
                    if (g[n].first == 0) {
                        res.push_back(n);
                    }
                }
                if (res.size() == start) return vector<int>();
                for (int i = start; i < res.size(); i++) {
                     for (auto e : g[res[i]].second) {
                         g[e].first--;
                     }
                    //set in-degree to -1 to mark delete. 
                     g[res[i]].first--;
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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