Cod sursa(job #1799660)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 6 noiembrie 2016 16:46:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

enum Color {
WHITE, GREY, BLACK
};

bool dfs(
    const vector<vector<int>>& graph,
    const int u,
    vector<Color>& colors,
    vector<int>& topologicalOrder) {
  colors[u] = Color::GREY;
  for (const int& v : graph[u]) {
    if ((colors[v] == Color::WHITE && dfs(graph, v, colors, topologicalOrder))
        || colors[v] == Color::GREY) {
      return true;
    }
  }
  topologicalOrder.push_back(u);
  colors[u] = Color::BLACK;
  return false;
}

vector<int> getTopologicalOrder(const vector<vector<int>>& graph) {
	const int size = int(graph.size());
	auto colors = vector<Color>(size, Color::WHITE);
	vector<int> topologicalOrder;
	for (int u = 0; u < size; ++u) {
		if (colors[u] == Color::WHITE && dfs(graph, u, colors, topologicalOrder)) {
			return vector<int>();
		}
	}
	reverse(topologicalOrder.begin(), topologicalOrder.end());
	return topologicalOrder;
}

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	int size, edges;
	in >> size >> edges;
	auto graph = vector<vector<int>>(size, vector<int>());
	for (; edges > 0; --edges) {
		int u, v;
		in >> u >> v;
		graph[u - 1].push_back(v - 1);
	}
	const auto topologicalOrder = getTopologicalOrder(graph);
	if (topologicalOrder.empty()) {
		out << "-1\n";
	} else {
		for (int i = 0; i < size; ++i) {
			out << topologicalOrder[i] + 1 << (i == size - 1 ? "\n" : " ");
		}
	}
	in.close();
	out.close();
	return 0;
}