Cod sursa(job #371803)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 6 decembrie 2009 23:42:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define MAXN 50010
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int N,M;
vector<int> G[MAXN];
stack<int> S;
int used[MAXN];

void get_input(){
	fi>>N>>M;
	int x,y;
	for (int i=1;i<=M;++i){
		fi>>x>>y;
		G[x].push_back(y);
	}
	fi.close();
}

void DFS(int nod){
	vector<int>::iterator it;
	used[nod]=1;
	for (it=G[nod].begin();it!=G[nod].end();++it)
		if (!used[*it]) DFS(*it);
	S.push(nod);
}

void get_output(){
	while (!S.empty()){
		fo<<S.top()<<" ";
		S.pop();
	}
	fo<<"\n";
	fo.close();
}

int main(){
	get_input();
	memset(used,0,sizeof(used));
	for (int i=1;i<=N;++i)
		if (!used[i]) DFS(i);
	get_output();
	return 0;
}