Cod sursa(job #1184785)

Utilizator pulseOvidiu Giorgi pulse Data 14 mai 2014 08:44:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>

using namespace std;

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

#define NMAX 50005

int n, m, v[NMAX], grad[NMAX], a[NMAX], ka;
vector <int> G[NMAX];

void sortare_top ()
{
    for (int i = 1; i <= n; ++i)
        if (grad[i] == 0)
            a[++ka] = i;
    for (int k = 1; k <= n; ++k)
    {
        int x = a[k];
        for (vector <int> :: iterator it = G[x].begin (); it != G[x].end (); ++it)
        {
            grad[*it]--;
            if (grad[*it] == 0)
                a[++ka] = *it;
        }
    }
}

int main ()
{
    fin >> n >> m;
    for (int i = 1, a, b; i <= m; ++i)
    {
        fin >> a >> b;
        G[a].push_back (b);
        grad[b]++;
    }
    sortare_top ();
    for (int i = 1; i <= ka; ++i)
        fout << a[i] << " ";
    fin.close (); fout.close ();
    return 0;
}