Cod sursa(job #2528756)

Utilizator Ioan_AnghelIoan Anghel Ioan_Anghel Data 22 ianuarie 2020 15:38:19
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int N = 1000001, M = 2000001;
int nr, vf[2 * M], urm[2 * M], lst[N], n, cnt = 0, st[N], pred[N];
bool viz[N];

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

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

int main()
{
    int n, m;
    in >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        in >> x >> y;
        adauga(x, y);
    }
    nr = 0;
    dfs(1);
    for(int i = n; i >= 1; i--){
        out << st[i] << " ";
    }

    return 0;
}