Cod sursa(job #525594)

Utilizator crushackPopescu Silviu crushack Data 25 ianuarie 2011 16:26:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <vector>
#define NMax 100000
using namespace std;

const char IN[]="sortaret.in",OUT[]="sortaret.out";

int N,M;
int culoare[NMax];
vector<int> a[NMax];
vector<int> Sol;

void bfs(int x)
{
	vector<int>::iterator it;
	culoare[x]=true;
	
	for (it= a[x].begin(); it<a[x].end();++it)
		if ( !culoare[*it] )
			bfs(*it);
	Sol.push_back(x);
}

int main()
{
	int i,x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
	{
		scanf("%d%d",&x,&y);
		a[x-1].push_back(y-1);
	}
	
	for (i=0;i<N;++i) if (!culoare[i])
		bfs(i);
	
	vector<int>::iterator it1,it2;
	
	for ( it1 = Sol.begin() , it2 = Sol.end() -1; it1<Sol.end() && it2>=Sol.begin() && 
		it1<it2;++it1,--it2)
		{
			int tmp= *it1;
			*it1=*it2;
			*it2=tmp;
		}
	
	freopen(OUT,"w",stdout);
	for (vector<int>::iterator it=Sol.begin(); it < Sol.end() ;++it)
		printf("%d ",*it+1);
	printf("\n");
	fclose(stdout);
	return 0;
}