Cod sursa(job #1451412)

Utilizator GilgodRobert B Gilgod Data 16 iunie 2015 22:42:01
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <list>

const char IN[] = "sortaret.in", OUT[] = "sortaret.out";
const int NMAX = 50001;
int time = 0;

using namespace std;

list<int> G[NMAX];
int N, M;
int discovery_time[NMAX];


inline void read_data() {
	freopen(IN, "r", stdin);
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int src, dst;
		scanf("%d %d", &src, &dst);
		G[src].push_back(dst);
	}
	fclose(stdin);
}

ofstream fout(OUT);

void DFS(int node){
	fout << node << " ";
	discovery_time[node] = ++time;
	for (const int n : G[node]) {
		if (discovery_time[n]) {
			printf("Eroare: Graf ciclic.\n"); exit(0);
		}
		DFS(n);
	}
}

int main(){
	read_data();
	for (int i = 1; i <= N; ++i) {
		if (!discovery_time[i]) DFS(i);
	}
	fout << endl;
	return 0;
}