Cod sursa(job #2149799)

Utilizator fylot3Bogdan Filote fylot3 Data 2 martie 2018 23:35:22
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <list>
#include <vector>

std::vector<COLOR> color;
std::list<int> sortedNodes;

enum COLOR
{
	WHITE, GREY, BLACK
};

class Graph {
	int V;
	std::list<int> *adj;

	void explore(int node);

public:
	Graph(int V);
	void addUndirectedEdge(int u, int v);
	void addDirectedEdge(int s, int d);

	/* Topological Sort */
	void TopologicalSort();
};

Graph::Graph(int V) {
	this->V = V;
	adj = new std::list<int>[V];
}

void Graph::addUndirectedEdge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void Graph::addDirectedEdge(int s, int d) {
	adj[s].push_back(d);
}

void Graph::TopologicalSort() {

	for (int i = 0; i < V; i++) {
		if (color[i] == WHITE) {
			explore(i);
		}
	}
}

void Graph::explore(int node) {
	color[node] = GREY;

	for (auto it = adj[node].begin(); it != adj[node].end(); it++) {
		if (color[*it] == WHITE) {
			color[*it] = GREY;
			explore(*it);
		}
	}

	color[node] = BLACK;
	sortedNodes.push_front(node + 1);
}

void printSolution() {
	std::ofstream fout("sortaret.out");
	for (auto it = sortedNodes.begin(); it != sortedNodes.end(); it++)
		fout << *it << " ";
}

int main(void) {
	int N, M, s, d;
	std::ifstream fin("sortaret.in");
	fin >> N >> M;

	Graph graph = Graph(N);
	color.resize(N, WHITE);
	for (int i = 0; i < M; i++) {
		fin >> s >> d;
		graph.addDirectedEdge(s - 1, d - 1);
	}

	graph.TopologicalSort();

	printSolution();

	return 0;
}