Cod sursa(job #2204340)

Utilizator DordeDorde Matei Dorde Data 15 mai 2018 15:44:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 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 , minval = (1 << 30);
    for(i = 1 ; i <= n ; ++ i)
        minval = min (dp [i] , minval);
    for(i = 1 ; i <= n ; ++ i)
        if(dp [i] == minval)
            q . push (i) , mark [i] = 1;
    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]] == 1 + dp [curent] )
                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;
}