Cod sursa(job #2419685)

Utilizator SternulStern Cristian Sternul Data 9 mai 2019 11:11:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n, m, x, y;

    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    f>>n>>m;
    vector <int> ord;
    vector <vector < int > > G(n);
    vector < int > grad(n, 0);
    for(int i = 0;i < m;i++)
    {
        f>>x>>y;
        x--;
        y--;
        grad[y]++;
        G[x].push_back(y);
    }
    queue <int> q;
    for(int i = 0;i < n;++i)
        if(grad[i] == 0) {
            grad[i] = -1;
            q.push(i);
        }
    while(!q.empty()){
        int nod_curent = q.front();
        q.pop();
        ord.push_back(nod_curent);
        for(auto nod: G[nod_curent]){
            grad[nod]--;
            if(grad[nod] == 0) {
                q.push(nod);
                grad[nod] = -1;
            }
        }
    }
    vector<int>::iterator p;
    for(p = ord.begin();p != ord.end();p++)
        g<<*p + 1<<" ";

    return 0;
}