Pagini recente » Cod sursa (job #1718337) | Cod sursa (job #1628239) | Cod sursa (job #1637572) | Cod sursa (job #246691) | Cod sursa (job #2668466)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
using namespace std;
int dfs(vector<list<int>>& graph, vector<bool>& visited, vector<int>& time, int start, int now) {
now++;
for (int i : graph[start]) {
if (!visited[i]) {
visited[i] = true;
now = dfs(graph, visited, time, i, now);
}
}
now++;
time[start] = now;
return now;
}
int main()
{
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");
int m, n;
fi >> n >> m;
vector<list<int>> graph(n);
for (int i = 0; i < m; i++) {
int a, b;
fi >> a >> b;
a--;
b--;
graph[a].push_back(b);
}
vector<bool> visited(n, false);
vector<int> time(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
now = dfs(graph, visited, time, i, now);
}
}
vector<pair<int, int>> topol;
for (int i = 0; i < n; i++) {
topol.push_back(pair<int, int>(i, time[i]));
}
sort(topol.begin(), topol.end(), [](pair<int, int> a, pair<int, int> b) { return a.second > b.second; });
for (auto& i : topol) {
fo << i.first + 1 << " ";
}
fi.close();
fo.close();
return 0;
}