Cod sursa(job #830567)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 7 decembrie 2012 07:49:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb

#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;
}