Course Schedule II Solutions in C++

// Source : https://leetcode.com/problems/course-schedule-ii/
// Author : Hao Chen
// Date   : 2015-06-10




class Solution {
public:
    // if has cycle, return false, else return true
    bool topologicalSort( int n, vector<int>& explored, vector<int>& path, 
                          unordered_map<int, vector<int>>& graph, 
                          vector<int>& result) 
    {
        
        for(int i=0; i<graph[n].size(); i++) {
            
            int prereq = graph[n][i];
            
            if ( path[prereq] ) {
                result.clear();
                return false;
            }
            
            path[prereq] = true;
            if (!topologicalSort(prereq, explored, path, graph, result)){
                result.clear();
                return false;
            }
            path[prereq] = false;
        }
        if (!explored[n]) {
            result.push_back(n);
        }
        explored[n] = true;
        return true;
    }

    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        
        vector<int> result;
        vector<int> enterance (numCourses, true);
        
        //using map to stroe the graph, it's easy to search the edge for each node
        //the bool in pair means it is explored or not
        unordered_map<int, vector<int>> graph;
        for(int i=0; i<prerequisites.size(); i++){
            graph[prerequisites[i].first].push_back( prerequisites[i].second );
            enterance[prerequisites[i].second] = false;
        }

        //explored[] is used to record the node already checked!
        vector<int> explored(numCourses, false);

        //path[] is used to check the cycle during DFS
        vector<int> path(numCourses, false);

        for(int i=0; i<numCourses; i++){
            if (!enterance[i] || explored[i]) continue;
            if (!topologicalSort(i, explored, path, graph, result)) return result;
        }
        //if there has one course hasn't been explored, means there is a cycle
        for (int i=0; i<numCourses; i++){
            if (!explored[i]) return vector<int>();
        }
        return result;
    }
};

/// Source : https://leetcode.com/problems/course-schedule-ii/
/// Author : liuyubobobo
/// Time   : 2018-12-16

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


/// Using Priority Queue
/// Time Complexity: O(ElogE)
/// Space Complexity: O(V + E)
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> pre(numCourses, 0);
        vector<vector<int>> g(numCourses);
        for(const pair<int, int>& p: prerequisites){
            int from = p.second;
            int to = p.first;
            g[from].push_back(to);
            pre[to] ++;
        }

        for(int i = 0; i < numCourses; i ++)
            pq.push(make_pair(pre[i], i));

        vector<bool> learnt(numCourses, false);
        vector<int> res;
        while(!pq.empty()){
            int x = pq.top().first;
            int id = pq.top().second;
            pq.pop();

            if(!learnt[id]){
                if(x) return {};

                res.push_back(id);
                learnt[id] = true;

                for(int next: g[id]){
                    pre[next] --;
                    pq.push(make_pair(pre[next], next));
                }
            }
        }

        return res;
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<pair<int, int>> pre1 = {{1,0}};
    print_vec(Solution().findOrder(2, pre1));
    // 0 1

    vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
    print_vec(Solution().findOrder(4, pre2));
    // 0 1 2 3

    return 0;
}

/// Source : https://leetcode.com/problems/course-schedule-ii/
/// Author : liuyubobobo
/// Time   : 2018-12-16

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


/// Using Queue is enough
/// Since we are only interested in 0-indegree vertex :-)
///
/// Time Complexity: O(E)
/// Space Complexity: O(V + E)
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

        vector<int> pre(numCourses, 0);
        vector<vector<int>> g(numCourses);
        for(const pair<int, int>& p: prerequisites){
            int from = p.second;
            int to = p.first;
            g[from].push_back(to);
            pre[to] ++;
        }

        queue<int> q;
        for(int i = 0; i < numCourses; i ++)
            if(pre[i] == 0)
                q.push(i);

        vector<int> res;
        while(!q.empty()){
            int id = q.front();
            q.pop();

            res.push_back(id);
            for(int next: g[id]){
                pre[next] --;
                if(pre[next] == 0)
                q.push(next);
            }
        }

        if(res.size() == numCourses)
            return res;
        return {};
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<pair<int, int>> pre1 = {{1,0}};
    print_vec(Solution().findOrder(2, pre1));
    // 0 1

    vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
    print_vec(Solution().findOrder(4, pre2));
    // 0 1 2 3

    return 0;
}

/// Source : https://leetcode.com/problems/course-schedule-ii/
/// Author : liuyubobobo
/// Time   : 2018-12-16

#include <iostream>
#include <vector>
#include <stack>

using namespace std;


/// Topological Order based on DFS
/// Time Complexity: O(V + E)
/// Space Complexity: O(V + E)
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

        vector<vector<int>> g(numCourses);
        for(const pair<int, int>& p: prerequisites){
            int from = p.second;
            int to = p.first;
            g[from].push_back(to);
        }

        if(hasCircle(g)) return {};
        return topoOrder(g);
    }

private:
    bool hasCircle(const vector<vector<int>>& g){

        vector<bool> visited(g.size(), false);
        vector<bool> onPath(g.size(), false);
        for(int i = 0; i < g.size(); i ++)
            if(!visited[i])
                if(circleDFS(g, i, visited, onPath))
                    return true;
        return false;
    }

    bool circleDFS(const vector<vector<int>>& g, int v,
                   vector<bool>& visited, vector<bool>& onPath){

        visited[v] = true;
        onPath[v] = true;
        for(int next: g[v])
            if(!visited[next]){
                if(circleDFS(g, next, visited, onPath))
                    return true;
            }
            else if(onPath[next])
                return true;

        onPath[v] = false;
        return false;
    }

    vector<int> topoOrder(const vector<vector<int>>& g){

        vector<bool> visited(g.size(), false);
        stack<int> st;
        for(int i = 0; i < g.size(); i ++)
            if(!visited[i])
                topoDFS(g, i, visited, st);

        vector<int> res;
        while(!st.empty()){
            res.push_back(st.top());
            st.pop();
        }
        return res;
    }

    void topoDFS(const vector<vector<int>>& g, int v, vector<bool>& visited, stack<int>& st){

        visited[v] = true;
        for(int next: g[v])
            if(!visited[next])
                topoDFS(g, next, visited, st);
        st.push(v);
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<pair<int, int>> pre1 = {{1,0}};
    print_vec(Solution().findOrder(2, pre1));
    // 0 1

    vector<pair<int, int>> pre2 = {{1,0},{2,0},{3,1},{3,2}};
    print_vec(Solution().findOrder(4, pre2));
    // 0 1 2 3

    return 0;
}