Cod sursa(job #546672)

Utilizator skullLepadat Mihai-Alexandru skull Data 5 martie 2011 12:44:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define nmax 50005

vector<int> G[nmax];
int n, viz[nmax], k, vec[nmax];

void citire ()
{
	int i, m, x, y;
	freopen("sortaret.in","r",stdin);
	scanf("%d %d ", &n, &m);
	for (i = 1; i <= m; ++i)
	{
		scanf("%d %d ", &x, &y);
		G[x].push_back(y);
	}
}

void dfs( int x )
{
	int i;
	viz[x] = 1;
	for (i = 0; i < G[x].size (); ++i)
		if ( !viz[G[x][i]] )
			dfs(G[x][i]);
	vec[++k] = x;
}

void solve ()
{
	int i;
	for (i = 1; i <= n; ++i)
		if ( !viz[i] )
			dfs(i);
}

void afisare ()
{
	int i;
	freopen("sortaret.out","w",stdout);
	for (i = n; i > 0; --i)
		printf("%d ", vec[i]);
}

int main ()
{
	citire ();
	solve ();
	afisare ();
	return 0;
}