Cod sursa(job #668051)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 24 ianuarie 2012 11:11:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <bitset>
using namespace std;

ifstream fi ("sortaret.in");
ofstream fo ("sortaret.out");

const int dim = 50005;
bitset <dim> viz;
struct nod { int v; nod *a; } *V[dim];
int N, M, T[dim];

void addnod (nod *&p, int x)
{
	nod *q = new nod;
	q->v = x;
	q->a = p;
	p = q;
}

void cit ()
{
	fi >> N >> M;
	for (int i = 1; i <= N; i++)
		V[i] = NULL;
	for (int i = 0, x, y; i < M; i++)
	{
		fi >> x >> y;
		addnod (V[x], y);
	}
	T[0] = N;
}

void dfs (int n)
{
	if (viz[n])
		return;
	viz[n] = 1;
	
	int f;
	for (nod *i = V[n]; i != NULL; i = i->a)
	{
		f = i->v;
		dfs (f);
	}
	T[T[0]--] = n;
}

void afi ()
{
	for (int i = 1; i <= N; i++)
		fo << T[i] << ' ';
}

int main ()
{
	cit ();
	for (int i = 1; i <= N; i++)
		dfs (i);
	afi ();
	return 0;
}