Cod sursa(job #1571777)

Utilizator cristinamateiCristina Matei cristinamatei Data 18 ianuarie 2016 15:04:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 50003;
const int M = 100003;

int nr, n, m, p, lst[N], vf[M], urm[M], sol[N], a[N], b[N], s;

void adauga( int x, int y )
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

int main()
{
    int i, x, y, k;
    in >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        in >> x >> y;
        a[y]++;
        adauga(x,y);
    }
    int p = 1, u = 0;
    for ( i = 1; i <= n; i++ )
        if ( a[i] == 0 )
        {
            u++;
            b[u] = i;
        }
    while( p <= u )
    {
        x = b[p];
        k = lst[x];
        while(k)
        {
            y = vf[k];
            a[y]--;
            if ( a[y] == 0 )
            {
                u++;
                b[u] = y;
            }
            k = urm[k];
        }
        p++;
    }
    for ( i = 1; i <= n; i++ )
        out << b[i]<<' ';
    return 0;
}