Cod sursa(job #797650)

Utilizator marinMari n marin Data 14 octombrie 2012 16:08:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <vector>
#define DIM 50010

using namespace std;

vector<int> L[DIM];
int S[DIM];
int v[DIM];
int N, M, i, x, y, s;


void dfs(int x) {
	v[x] = 1;
	int i;
	for (i=0;i<L[x].size();i++)
		if (!v[L[x][i]])
			dfs(L[x][i]);
	S[++s] = x;
}

int main() {
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");
	f>>N>>M;
	
	for (i=1;i<=M;i++) {
		f>>x>>y;
		L[x].push_back(y);
	}
	
	for (i=1;i<=N;i++)
		if (!v[i])
			dfs(i);
	
	for (i=N;i>=1;i--)
		g<<S[i]<<" ";
	f.close();
	g.close();
	return 0;
}