Cod sursa(job #2576187)

Utilizator kodama cheama alex koda Data 6 martie 2020 17:47:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

const int N = 50002;
const int M = 100002;
int lst[N], vf[2*M], urm[2*M], nr;
bool viz[N];
int topostack[N], svf;

void adauga (int x, int y) {
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs (int x) {
    viz[x] = true;
    for ( int p = lst[x]; p; p = urm[p] ) {
        int y = vf[p];
        if ( !viz[y] )
            dfs(y);
    }
    topostack[svf++] = x;
}

int main () {
    ifstream fin ("sortaret.in");
    ofstream fout ("sortaret.out");
    int n, m, x, y;
    fin>>n>>m;
    for ( int i = 0; i < m; i++ ) {
        fin>>x>>y;
        adauga(x,y);
    }
    for ( int i = 1; i <= n; i++ ) {
        if (!viz[i])
            dfs(i);
    }
    for ( int i = n-1; i >= 0; i-- ) {
        fout<<topostack[i]<<" ";
    }
    return 0;
}