Cod sursa(job #2918652)

Utilizator bumblebeeGeorge Bondar bumblebee Data 12 august 2022 12:51:19
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#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;
}