Pagini recente » Cod sursa (job #1952777) | Profil andrici_cezar | Cod sursa (job #846684) | Cod sursa (job #2569718) | Cod sursa (job #1799659)
#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;
}