Pagini recente » Istoria paginii tygyn/solutie_romana | Cod sursa (job #1785004) | Cod sursa (job #2565532) | Cod sursa (job #1149537) | Cod sursa (job #2204335)
#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);
while(q . size ())
{
int curent = q . front ();
printf ("%d " , curent );
int sz = v [curent] . size ();
for(i = 0 ; i < sz ; ++ i)
if(dp [v [curent][i]] == 1 + dp [curent] && ! mark [v [curent][i]])
q . push (v [curent][i]) , mark [v[curent][i]] = 1;
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] = 1 + dp [a];
}
bfs ();
puts("");
return 0;
}