Cod sursa(job #2204341)

Utilizator DordeDorde Matei Dorde Data 15 mai 2018 15:46:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include<bitset>
using namespace std;
char const in [] = "sortaret.in";
char const out [] = "sortaret.out";
int const NM = 5e4 + 7  /*NM2  = 1e5 + 7;*/ ;
int n;
int dp [NM];
vector <int> v [NM];
queue <int> q;
bitset <NM> mark;
void bfs ()
{
    int i ;
    for(i = 1 ; i <= n ; ++ i)
        if(! dp [i])
            q . push (i) ;
    while(q . size ())
    {
        int curent = q . front ();
        printf ("%d " , curent );
        int sz = v [curent] . size ();
        for(i = 0 ; i < sz ; ++ i)
        {
            -- dp [v [curent][i]];
            if(! dp [v [curent][i]] )
                q . push (v [curent][i]) ;
        }
        q . pop ();
    }
}
int main()
{
    int m;
    freopen (in , "r" , stdin);
    freopen (out , "w" , stdout);
    scanf ("%d %d\n" , &n , &m);
    for(int i = 1 ; i <= m ; ++ i)
    {
        int a , b;
        scanf ("%d %d\n" , &a , &b);
        v [a] . push_back (b);
        ++ dp [b] ;
    }
    bfs ();
    puts("");
    return 0;
}