Pagini recente » Cod sursa (job #1342654) | Cod sursa (job #1530720) | Cod sursa (job #50914) | Cod sursa (job #2003612) | Cod sursa (job #830567)
Cod sursa(job #830567)
#include <cstdio>
const int MAX_SIZE(50001);
int n, m;
int income [MAX_SIZE];
int queue [MAX_SIZE], *push(queue), *pop(queue);
struct edge
{
int node;
struct edge *next;
} *graph [MAX_SIZE];
inline void add (int x, int y)
{
struct edge *new_edge(new struct edge);
new_edge->node = y;
new_edge->next = graph[x];
graph[x] = new_edge;
}
inline void read (void)
{
std::freopen("sortaret.in","r",stdin);
std::scanf("%d%d",&n,&m);
int x, y;
for (int counter(0) ; counter < m ; ++counter)
{
std::scanf("%d %d",&x,&y);
add(x,y);
++income[y];
}
std::fclose(stdin);
}
inline void Kahn (void)
{
struct edge *iterator;
int vertex;
for (int index(1) ; index <= n ; ++index)
if (!income[index])
{
*push = index;
++push;
}
while (pop < push)
{
vertex = *pop;
++pop;
for (iterator = graph[vertex] ; iterator ; iterator = iterator->next)
{
--income[iterator->node];
--m;
if (!income[iterator->node])
{
*push = iterator->node;
++push;
}
}
}
// If m > 0 there is a cycle
}
inline void print (void)
{
std::freopen("sortaret.out","w",stdout);
for (int *iterator(queue) ; iterator < push ; ++iterator)
std::printf("%d ",*iterator);
std::putchar('\n');
std::fclose(stdout);
}
int main (void)
{
read();
Kahn();
print();
return 0;
}