Cod sursa(job #1255845)

Utilizator Stefanescu_MihaiStefanescu Mihai-Nicolae Stefanescu_Mihai Data 5 noiembrie 2014 11:55:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
using namespace std;

#define fileIn "sortaret.in"
#define fileOut "sortaret.out"
#define maxN 50030
#define maxM 100050

vector <int> vec[maxN];
int prevk[maxN];

int q[maxN];
int first = 1, last;

void addQ( int x )
{
    q[++last] = x;
}

int getQ()
{
    if ( first > last )
        return 0;

    ++first;

    return q[first-1];
}


int main()
{
    ifstream sIn( fileIn );
    ofstream sOut( fileOut );

    int n, m, i;
    sIn >> n >> m;

    int x, y;
    int first;
    for ( i = 1; i <= m; ++i )
    {
        sIn >> x >> y;
        vec[x].push_back( y );
        ++prevk[y];
    }

    for ( i = 1; i <= n; ++i )
    {
        if ( !prevk[i] )
            addQ( i );
    }

    int c = getQ();
    int size;
    while ( c )
    {
        sOut << c << ' ';

        size = vec[c].size();
        for ( i = 0; i < size; ++i )
        {
            --prevk[ vec[c][i] ];
            if ( !prevk[ vec[c][i] ] )
                addQ( vec[c][i] );
        }

        c = getQ();
    }


    sOut << '\n';


    return 0;
}