Cod sursa(job #680732)

Utilizator informatician28Andrei Dinu informatician28 Data 15 februarie 2012 21:08:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<cstdio> 
#include<vector> 
#define DIM 50001
#define pb push_back
using namespace std;
int N, M;
bool viz[DIM];
vector< int > G[DIM];
vector< int > sol;

void DFs(int nod)
{
	viz[nod] = true;
	for(vector< int >:: iterator it = G[nod].begin(); it != G[nod].end(); ++it )
		if( viz[*it] == false )
			DFs(*it);
	sol.pb(nod);
}

int main()
{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	int x, y, i;
	
	scanf("%d%d", &N, &M);
	for(i = 0; i < M; i++)
	{
		scanf("%d%d", &x, &y);
		G[x].pb(y); 
	}
	for(i = 1; i <= N; i++)
		if( viz[i] == false ) 
			DFs(i);
	for( i = sol.size()-1; i >= 0; i-- )
		printf("%d ", sol[i]);
	return 0;
}