Cod sursa(job #809596)

Utilizator cnt_tstcont teste cnt_tst Data 8 noiembrie 2012 18:38:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <fstream>
#include <vector>
#define DIM 50010

using namespace std;

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

void dfs(int x) {
	v[x] = 1;
	for (int i=0;i<L[x].size();i++)
		if (v[L[x][i]] == 0)
			dfs(L[x][i]);
	S[++k] = 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);
		G[y] = 1;
	}
	
	for (i=1;i<=N;i++)
		if (!G[i])
			dfs(i);
	for (i=k;i>=1;i--)
		g<<S[i]<<" ";
	return 0;
}