Leetcode 210: Course Schedule II

210.cpp

#include<bits/stdc++.h>
using namespace std;

class Solution{
  public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
      vector<int> seq;
      // 0 -> not visited
      // 1 -> visiting
      // 2 -> already left
      vector<int> status(numCourses+1,0);
      vector<vector<int>> edges(numCourses+1,vector<int>());
      for(auto& p:prerequisites){
        edges[p.second].push_back(p.first);
      }
      for(int i=0;i<numCourses;++i){
        edges[numCourses].push_back(i); //superNode, process disconnected graph
      }
      if(DFS(numCourses,edges,status,seq)){
        reverse(seq.begin(),seq.end()); // make seq finishing time from ascending to descending
        return vector<int>(seq.begin()+1,seq.end());
      }
      else return {};  
    }
    bool DFS(int s,vector<vector<int>>& edges,vector<int>& status,vector<int>& seq){
      if(status[s] == 0){
        status[s] = 1;
        for(int& v:edges[s]){
          bool b = DFS(v,edges,status,seq);
          if(!b) return false;
        }
        status[s] = 2;// seq. will follow the finish time in ascending order
        seq.push_back(s);
        return true;
      }
      else if(status[s] == 2) return true;
      else return false;
    }
};

int main(){
  Solution sol;
  vector<pair<int,int>> prerequisites({{1,2},{2,1}});
  cout << sol.findOrder(3,prerequisites) << endl;
}