Mai intai trebuie sa te autentifici.
Cod sursa(job #1799656)
Utilizator | Data | 6 noiembrie 2016 16:41:31 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.48 kb |
#include <fstream>
#include <vector>
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<int>(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;
}