Cod sursa(job #494613)

Utilizator klamathixMihai Calancea klamathix Data 22 octombrie 2010 12:17:59
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<cstdio>
#include<vector>
const int maxn = 105000;
using namespace std;

int i , j , n, m , a, b , v;
vector <int> G[maxn];
bool seen[maxn];
int sol[maxn];

void DF( int node ) { 
	seen[node] = 1;
	for( i = 0 ; i< G[node].size() ; ++i )  
		if ( !seen[G[node][i]]) 
			DF( G[node][i]);
	sol[++v] = node;
}


int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	for( i = 1 ; i <= m ; ++i ) { 
		scanf("%d %d",&a,&b);
		G[a].push_back(b);
	}
	
	for( i = 1 ; i <= n ; ++i ) 
		if ( !seen[i]) 
			DF(i);
	for( i = v ; i >= 1 ; --i ) 
		printf("%d ",sol[i]);
	
return 0;
}