Cod sursa(job #602505)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 11 iulie 2011 18:06:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <vector>
#include <string.h>

#define max_n 50001

using namespace std;

int i,n,m,x,y,nst;
bool u[max_n];
vector <int> g[max_n];
vector <int>::iterator it;
int st[max_n];

ifstream in("sortaret.in");
ofstream out("sortaret.out");

void DF(int x) {
	vector <int>::iterator it;
	u[x]=true;
	for (it=g[x].begin(); it!=g[x].end(); it++) 
		if (!u[*it]) DF(*it);
	st[nst++]=x;
}

int main () {
	in >> n >> m;
	for (i=1; i<=m; i++) {
		in >> x >> y;
		g[x].push_back(y);
	}
	
	nst=0;
	memset(u,false,sizeof(u));
	for (i=1; i<=n; i++) 
		if (!u[i]) DF(i);
	for (i=n-1; i>=0; i--) 
		out << st[i] << ' ';
	out << '\n';
	return 0;
}