Cod sursa(job #2533645)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 29 ianuarie 2020 15:28:34
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

int vf[100005], urm[100005], lst[100005], nrp[50005], v[50005];
int nr, n, m, x, k;

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

bool viz[50005];

void sortare_topologica(int x) {
    viz[x] = true;
    for(int p = lst[x]; p; p = urm[p])
        if(!viz[vf[p]])
            sortare_topologica(vf[p]);
    v[++k] = x;
}

int main() {
    int x, y;
    fin >> n >> m;
    do {
        fin >> x >> y;
        adauga(x, y);
    } while(--m);
    sortare_topologica(1);

    for(int i = k ; i > 0; --i)
        fout << v[i] << ' ';

    fin.close(); fout.close();
    return 0;
}