Cod sursa(job #1451417)

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

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

enum{WHITE, GREY, BLACK};

using namespace std;

list<int> G[NMAX];
int N, M;
int state[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);
list<int> Vs;

void DFS(int node){
	fout << node << " ";
	state[node] = GREY;
	for (const int n : G[node]) {
		if (state[n] == GREY) {
			printf("Eroare: Graf ciclic.\n"); exit(0);
		}
		if(state[n] == WHITE) DFS(n);
	}
	state[node] = BLACK;
	Vs.push_front(node);
}

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