Cod sursa(job #584089)

Utilizator XbyteAvram Florin Xbyte Data 23 aprilie 2011 21:16:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<cstdio>
#include<vector>

using namespace std;

const int MaxN = 50001;
const char InFile[] = "sortaret.in";
const char OutFile[] = "sortaret.out";

int N,M,sol[MaxN],viz[MaxN];
vector< vector<int> > G;

void DFS(int nod)
{
	vector<int>::iterator it,iend;
	it = G[nod].begin();
	iend = G[nod].end();
	viz[nod] = 1;
	for( ; it != iend ; ++it )
		if( !viz[*it] )
			DFS(*it);
	sol[++sol[0]] = nod;
}

int main()
{
	freopen( InFile , "r" , stdin );
	freopen( OutFile , "w" , stdout );
	scanf("%d%d" , &N , &M );
	G.resize(N+1);
	int i,x,y;
	for( i = 0 ; i < M ; i++ )
		{
			scanf("%d%d" , &x , &y );
			G[x].push_back(y);
		}
	for( i = 1 ; i <= N ; i++ )
		if( !viz[i] )
			DFS(i);
	for( i = N; i ; --i )
		printf("%d " , sol[i] );
	printf("\n");
	return 0;
}