Cod sursa(job #2419672)

Utilizator SternulStern Cristian Sternul Data 9 mai 2019 10:45:56
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 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 < n;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)
            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);
        }
    }
    vector<int>::iterator p;
    for(p = ord.begin();p != ord.end();p++)
        g<<*p + 1<<" ";

    return 0;
}