Cod sursa(job #2202840)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 10 mai 2018 08:37:58
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <queue>
#include <list>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct lista{
    list<int> urm;
    list<int> ant;
}v[5000];

queue<int> q;
list<int>::iterator it, it2;

int main()
{
    int  i, j, M, N, x, y;

    fin >> N >> M;

    for( i = 1; i <= M; i++) fin >> x >> y,
        v[x].urm.push_back(y), v[y].ant.push_back(x);

    for( i = 1; i <= N; i++) if(v[i].ant.empty())
        q.push(i), fout << i << " ";

    while(!q.empty())
    {
        x = q.front(), q.pop();
        for(it = v[x].urm.begin(); it != v[x].urm.end(); it++)
        {
            y = *it;
            for(it2 = v[y].ant.begin(); it2 != v[y].ant.end(); it2++){
                if( *it2 == x ) v[y].ant.erase(it2);break;}
            if(v[y].ant.empty())
                q.push(y), fout << y << " ";
        }
    }

    return 0;
}