Cod sursa(job #1382345)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 8 martie 2015 21:03:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <vector>
#include <fstream>

enum Color { WHITE, GREY, BLACK };

class Vertex {
public:
	int index;
	std::vector<int> neighbours;

	Vertex() : index(-1) {}
	Vertex(int index) : index(index) {}

	void addNeighbour(int neighbourIndex) {
		neighbours.push_back(neighbourIndex);
	}
};

std::ifstream fin ("sortaret.in");
std::ofstream fout("sortaret.out");

std::vector<Color> colors(50001, WHITE);
std::vector<Vertex> vertex(50001);
std::vector<int> result;

void DFS(int index) {
	colors[index] = GREY;
	for (int i = 0; i < vertex[index].neighbours.size(); ++i) {
		int nIndex = vertex[index].neighbours[i];
		if (colors[nIndex] == WHITE) {
			DFS(nIndex);
		}
	}
	colors[index] = BLACK;
	fout << index << ' ';
}

int main() {
	int N, M;

	fin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int from, to;
		fin >> from >> to;
		vertex[from].addNeighbour(to);
	}

	for (int i = 1; i <= N; ++i) {
		if (colors[i] == WHITE) {
			DFS(i);
		}
	}

	return 0;
}