Cod sursa(job #354290)

Utilizator bogdanacmDrutu Bogdan bogdanacm Data 7 octombrie 2009 17:27:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 50005
#define pb push_back

vector <int> G[NMAX];
int N,M;
int viz[NMAX];
vector <int> D;

void DFS(int k)
{
	int i;
	viz[k] = 1;
	
	for (i=0;i<G[k].size();i++)
		if(!viz[G[k][i]])
			DFS(G[k][i]);
	D.pb(k);//printf("%d ",k);
}

int main()
{
	int i,a,b;
	
	freopen("sortaret.in","rt",stdin);
	freopen("sortaret.out","wt",stdout);
	
	scanf("%d %d",&N,&M);
	for (i=0;i<M;i++)
	{
		scanf("%d %d",&a,&b);
		G[a].pb(b);
	}
	for (i=1;i<=N;i++)
		if (!viz[i])
			DFS(i);

	for (i=N-1;i>=0;i--)
		printf("%d ",D[i]);

	return 0;
}