Course Schedule

input/code.cpp: In function 'std::vector<int> top_sort(const std::vector<std::vector<int> >&)':
input/code.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0; i<state.size(); i++){
      |                  ~^~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i=0; i< sol.size(); i++){
      |                      ~^~~~~~~~~~~~
input/code.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if(i!=sol.size()-1)cout << " ";
      |                ~^~~~~~~~~~~~~~

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

using namespace std;

bool dfs(const vector<vector<int>>& adj, stack<int>& s, vector<int>& state, vector<int>& sol){
    int nod = s.top();
    s.pop();
    if(state[nod]==1)return false;
    state[nod]=1;
    for(auto i: adj[nod]){
        if(state[i]!=2){
            s.push(i);
            if(!dfs(adj,s,state,sol))return false;
        }
    }
    state[nod]=2;
    sol.push_back(nod);
    return true;
}

vector<int> top_sort(const vector<vector<int>>& adj){
    stack<int> s;
    vector<int> state(adj.size(), 0);

    vector<int> sol;
    for(int i=0; i<state.size(); i++){
        if(state[i]==0){
            s.push(i);
            bool res = dfs(adj,s,state,sol);
            if(!res)return vector<int>(1,-1);
        }
    }
    vector<int> gir;
    for(int i=sol.size()-1; i>=0; i--)gir.push_back(sol[i]);

    return gir;


}

int main(){
    int n,m;
    cin >> n >> m;

    vector<vector<int>> adj(n);

    for(int i=0;i<m; i++){
        int a,b;
        cin >> a >> b;
        adj[a-1].push_back(b-1);
    }

    vector<int> sol = top_sort(adj);

    if(sol[0]==-1)cout << "IMPOSSIBLE" << endl;

    else{
        for(int i=0; i< sol.size(); i++){
            cout << sol[i]+1;
            if(i!=sol.size()-1)cout << " ";
        }
        cout << endl;
    }


}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED