Cod sursa(job #2422199)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 17 mai 2019 18:58:59
Problema Sortare topologica Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

vector< vector< int > > g(50005);
vector< int > inv(50005);
vector< int > l, s;

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

    int x, y;
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        g[x].push_back(y);
        inv[y]++;
    }

    for(int i = 1; i <= n; i++) {
        if(inv[i] == 0) s.push_back(i);
    }

    while(s.size()) {
        int a = s[0];
        s.erase(s.begin());
        l.push_back(a);
        for(int i = 0; i < g[a].size(); i++) {
            inv[g[a][i]]--;
            if(inv[g[a][i]] == 0) s.push_back(g[a][i]);
        }
    }

    for(int i = 0; i < l.size(); i++) {
        cout << l[i] << " " ;
    }
}