Cod sursa(job #2970232)

Utilizator AntoniuFicAntoniu Ficard AntoniuFic Data 24 ianuarie 2023 17:54:51
Problema Sortare topologica Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define sz 500

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m, noduri[sz];
int nrVecini[sz], vecini[sz][sz];
int desc[sz], finalizare[sz];

void dfs(int start, int &timp) {
    if (desc[start] != 0) {
        return;
    }
    desc[start] = timp++;
    for (int i = 0; i < nrVecini[start]; i++) {
        dfs(vecini[start][i], timp);
    }
    finalizare[start] = timp++;
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        vecini[x - 1][nrVecini[x - 1]++] = y - 1;
    }
    int timp = 1;
    for (int i = 0; i < n; ++i) {
        dfs(i, timp);
    }
    for (int i = 0; i < n; ++i) {
        noduri[i] = i + 1;
    }

    bool ok;

    do {
        ok = false;
        for (int i = 0; i < n - 1; ++i) {
            if (finalizare[i] < finalizare[i + 1]) {
                int aux = noduri[i + 1];
                noduri[i + 1] = noduri[i];
                noduri[i] = aux;
                ok = true;
                aux = finalizare[i];
                finalizare[i] = finalizare[i + 1];
                finalizare[i + 1] = aux;
            }
        }
    } while (ok);
    for (int i = 0; i < n; ++i) {
        fout << noduri[i] << " ";
    }
    return 0;
}