Course Schedule

input/code.cpp: In function 'std::__cxx11::list<int> topological_sort(graph&)':
input/code.cpp:24:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for (int i = 0; i < G[u].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
input/code.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i = 0; i < G[u].size();++i) {
      |                        ~~^~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:74:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::list<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     if(L.size() != n)
      |        ~~~~~~~~~^~~~

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <list>
using namespace std;

typedef vector<vector<int>> graph;

void read_graph(graph& G, int n, int m) {
    for (int i = 0; i < m; ++i) {
            int v1, v2;
            cin >> v1 >> v2;
            G[v1-1].push_back(v2-1);
        }
}

list<int> topological_sort(graph& G) {
    int n = G.size();
    vector<int> ge(n,0);

    // Count number of previos courses
    for (int u = 0; u < n; ++u) {
        for (int i = 0; i < G[u].size(); ++i) {
            ++ge[G[u][i]];
        }
    }

    // Available courses
    priority_queue<int, vector<int>, greater<int>> S;

    // Add those courses without requisites
    for (int i = 0; i < n; ++i) {
        if (ge[i] == 0) S.push(i);
    }

    list<int> L;
    while (not S.empty()) {
        int u = S.top();
        S.pop();
        L.push_back(u); // Complete course u

        for(int i = 0; i < G[u].size();++i) {
            int v = G[u][i];
            --ge[v];
            // All needed courses for v have been completed before
            // Course v is now available
            if(ge[v] == 0) S.push(v);
        }
    }

    return L;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    graph G(n);
    read_graph(G,n,m);

    /*
    cout << "The graph is: " << endl;
    for (int i = 0; i < G.size(); ++i) {
        for (int j = 0; j < G[i].size(); ++j) {
            cout << G[i][j] << " ";
        }
        cout << endl;
    }
    */

    list<int> L = topological_sort(G);

    if(L.size() != n)
        cout << "IMPOSSIBLE" << endl;
    else {
        list<int>::const_iterator it = L.begin();
        while (it != L.end()) {
            if (it != L.begin()) cout << ' ';
            cout << (*it) + 1;
            ++it;
        }

        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