Cod sursa(job #1997446)

Utilizator cristinamateiCristina Matei cristinamatei Data 4 iulie 2017 13:13:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N = 50001;
const int M = 100001;
int lst[N], urm[M], vf[M], nr, nrp[N], q[M];
int n, m, k;

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

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

void bfs()
{
    int p, u, poz, i, y, x;
    p = 0;
    u = 0;
    for ( i = 1; i <= n; i++ )
        if ( nrp[i] == 0 )
            q[++u] = i;

    while( p < u )
    {
        p++;
        x = q[p];
        out << x<<' ';
        poz = lst[x];
        while( poz != 0 )
        {
            y = vf[poz];
            --nrp[y];
            if ( nrp[y] == 0 )
                q[++u] = y;
            poz = urm[poz];
        }
    }
}

int main()
{
    int x, y, i;
    in >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        in >> x >> y;
        adauga(x, y);
    }
    bfs();

    return 0;
}