Cod sursa(job #1357151)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 23 februarie 2015 19:48:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;

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

const int N = 50001, M = 100001;

int n, m;
int lst[N], vf[M], urm[M];
int sub[N];
int rez[N], nrrez = 0;
int nr = 0;
bool ok[N];

void sortaret_dfs(int x)
{
    ok[x] = 1;
    int p, y;
    p = lst[x];
    while(p != 0)
    {
        y = vf[p];
        if(!ok[y])
            sortaret_dfs(y);
        p = urm[p];
    }
    rez[++nrrez] = x;
}

void citire()
{
    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;

        vf[++nr] = y;
        urm[nr] = lst[x];
        lst[x] = nr;
        sub[x]++;
    }
}

void afisare()
{
    for(int i = nrrez; i >= 1; i--)
        out << rez[i] << ' ';
    out << '\n';
}

int main()
{
    citire();
    for(int i = 1; i <= n; i++)
        if(!ok[i])
            sortaret_dfs(i);
    afisare();
    return 0;
}