C++ clean topo sort solution


  • 0

    The key point is to give 3 states to each course.
    0 means a course isn't visited yet.
    1 means a course is VISITED but it still waits for its prerequisites to finish, i.e, it's not finished.
    2 means a course is finished.
    So in each recursion, we first mark a course as 1, and try to finish all its prerequisites. If one of its prerequisites also has state 1, it means there's a cycle and we should stop going deeper by returning false. If all its prerequisites are finished, then we can finish the current course and mark it as 2 and put it into the order list. By doing these to each graph, we can get a valid course order.

        vector<int> findOrder(int n, vector<pair<int, int>>& pres) {
            vector<vector<int>> edges(n);
            for (auto pre : pres) {
                edges[pre.first].push_back(pre.second);
            }
            vector<int> order;
            vector<int> finished(n, 0);
            for (int i = 0; i < n; ++i) {
                if (!finish(i, edges, finished, order))
                    return vector<int>();
            }
            return order;
        }
        
        bool finish(int course, vector<vector<int>> &edges, vector<int> &finished, vector<int> &order) {
            if (finished[course] == 1) return false;
            if (finished[course] == 2) return true;
            finished[course] = 1;
            for (int i : edges[course]) {
                if (!finish(i, edges, finished, order))
                    return false;
            }
            finished[course] = 2;
            order.push_back(course);
            return true;
        }
    

Log in to reply
 

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