Cod sursa(job #830568)

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

#include <cstdio>

const int MAX_SIZE(50001);

int n, m;
bool search [MAX_SIZE];
int stack [MAX_SIZE], *push(stack);

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);
	}
	std::fclose(stdin);
}

void DepthFirstSearch (int vertex)
{
	search[vertex] = true;
	for (struct edge *iterator(graph[vertex]) ; iterator ; iterator = iterator->next)
		if (!search[iterator->node])
			DepthFirstSearch(iterator->node);
	*push = vertex;
	++push;
}

inline void Tarjan (void)
{
	for (int index(1) ; index <= n ; ++index)
		if (!search[index])
			DepthFirstSearch(index);
}

inline void print (void)
{
	std::freopen("sortaret.out","w",stdout);
	for (int *pop(push - 1) ; pop >= stack ; --pop)
		std::printf("%d ",*pop);
	std::putchar('\n');
	std::fclose(stdout);
}

int main (void)
{
	read();
	Tarjan();
	print();
	return 0;
}