Cod sursa(job #2400376)

Utilizator dragostanTantaru Dragos Constantin dragostan Data 8 aprilie 2019 17:58:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>

using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
const int MAXN = 50001, MAXM = 100001;

int lst[MAXN], vf[MAXM], urm[MAXM], viz[MAXN],  af[MAXN];
int n, m, nr, cnt;
void adauga(int, int);
void dfsTop(int x);
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        adauga(x, y);
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!viz[i])
            dfsTop(i);
    }
    for(int i = cnt; i >= 1; --i)
    {
        cout << af[i] << ' ';
    }
    return 0;
}

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

void dfsTop(int x)
{
    int p, y;
    viz[x] = 1;
    p = lst[x];
    while(p)
    {
        y = vf[p];
        if(!viz[y])
        {
            dfsTop(y);
        }
        p = urm[p];
    }
    af[++cnt] = x;
}