Pagini recente » Cod sursa (job #2528656) | Cod sursa (job #1231282) | Cod sursa (job #499813) | Cod sursa (job #1653932) | Cod sursa (job #2918652)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 50000
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> g[MAXN + 1];
int visited_vertices[MAXN + 1], currentTime, finishingTimes[MAXN + 1];
bool cmp(int a, int b) {
return (b < a);
}
void computeFinishingTime(int currentVertex) {
finishingTimes[currentVertex] = ++currentTime;
for (int &neighbour : g[currentVertex]) {
if (!visited_vertices[neighbour]) {
visited_vertices[neighbour] = 1;
computeFinishingTime(neighbour);
}
}
finishingTimes[currentVertex] = ++currentTime;
}
int main() {
int n, m, nodeA, nodeB;
fin >> n >> m;
for (int i = 0; i < m; ++i) {
fin >> nodeA >> nodeB;
g[nodeA].push_back(nodeB);
}
computeFinishingTime(1);
// for (int i = 1; i <= n; ++i) {
// cout << "node = " << i << ", time = " << finishingTimes[i] << endl;
// }
for (int i = 1; i <= n; ++i) {
int maxTime = 0, currentVertex = 1;
for (int j = 1; j <= n; ++j) {
if (finishingTimes[j] > maxTime) {
maxTime = finishingTimes[j];
currentVertex = j;
}
}
fout << currentVertex << " ";
finishingTimes[currentVertex] = 0;
}
//sort(finishingTimes.begin(), finishingTimes.end(), cmp);
return 0;
}