Cod sursa(job #476246)

Utilizator mottyMatei-Dan Epure motty Data 10 august 2010 13:09:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<vector>

using namespace std;

const int N=50001;

vector <int> g[N];

int n, ts[N], p;

bool viz[N];

void Read()
{
	int m;
	scanf( "%d%d",&n,&m);
	
	int a, b;
	for( int i=1; i<=m; ++i)
	{
		scanf( "%d%d", &a, &b);
		g[a].push_back(b);
	}
}

void Df(int i)
{
	int aux;
	viz[i]=1;
	int sz=g[i].size();
	for( int j=0; j<sz; ++j)
	{
		aux=g[i][j];
		if(!viz[aux])
			Df(aux);
	}
	ts[++p]=i;
}

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

void Print()
{
	for( int i=n; i; --i)
		printf( "%d ", ts[i]);
}

int main()
{
	freopen( "sortaret.in", "r", stdin);
	freopen( "sortaret.out", "w", stdout);
	
	Read();
	Solve();
	Print();
	
	return 0;
}