No210_CourseScheduleII.cpp

// 210. Course Schedule II

// There are a total of n courses you have to take, labeled from 0 to n - 1.

// Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

// Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

// There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

// For example:

// 2, [[1,0]]
// There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

// 4, [[1,0],[2,0],[3,1],[3,2]]
// There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

// Note:
// The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
// You may assume that there are no duplicate edges in the input prerequisites.
// click to show more hints.

// Hints:
// This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
// Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
// Topological sort could also be done via BFS.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> s;
        if(numCourses == 0){
            return s;
        }
        adj = new list<int>[numCourses];
        for(auto &item : prerequisites){
            adj[item.first].push_back(item.second);
        }
        bool *visited = new bool[numCourses];
        bool *on_stack = new bool[numCourses];
        for(int i=0; i<numCourses; i++){
            visited[i] = false;
            on_stack[i] = false;
        }
        bool flag = true;
        
        // topological_sort(0, flag, on_stack, visited, s);
        for(int v=0; v<numCourses; v++){
            if(!visited[v])
                topological_sort(v, flag, on_stack, visited, s);
            if(!flag)
                break;
        }

        if(flag){
            return s;
        }
        else{
            s.clear();
            return s;
        }
    }
private:
    list<int> *adj;
    void topological_sort(int v, bool &flag, bool on_stack[], bool visited[],vector<int> &s){
        visited[v] = true;
        on_stack[v] = true;
        for(auto i = adj[v].begin(); i!=adj[v].end(); i++){
            if(!visited[*i]){
                topological_sort(*i, flag, on_stack, visited, s);
            }
            else if(visited[*i] && on_stack[*i]){
                flag = false;
                return;
            }
        }
        s.push_back(v);
        on_stack[v] = false;
    }
};