Cod sursa(job #606580)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 4 august 2011 21:17:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
# include <fstream>
# include <queue>
# include <vector>
using namespace std;

ifstream f ("sortaret.in");
ofstream g ("sortaret.out");
int n, m, x, y, ap[50010];
vector <int> A[50010];
queue <int> Q;
int main ()
{
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
        f >> x >> y, A[x].push_back (y), ++ap[y];
    for (int i = 1; i <= n; ++i)
        if (!ap[i]) Q.push (i), g << i;
    for (; !Q.empty (); Q.pop ())
    {
        int ret = Q.front ();
        for (vector <int> :: iterator it = A[ret].begin (); it != A[ret].end (); ++it)
            if (ap[*it])
            {
                --ap[*it];
                if (!ap[*it]) g << *it << ' ';
                Q.push (*it);
            }
    }
    g.close ();
    return 0;
}