Cod sursa(job #1376355)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 5 martie 2015 17:10:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

#define N 50001
#define M 100001
using namespace std;

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

int n, m;
bool ok[N];
int rez[N], nrez = 0;

int lst[N], vf[M], urm[M], nvf = 0;

void df(int x)
{
    ok[x] = 1;

    for(int i = lst[x]; i; i = urm[i])
    {
        int y = vf[i];

        if(!ok[y])
            df(y);
    }
    rez[++nrez] = x;
}

int main()
{
    in >> n >> m;

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

        vf[++nvf] = y;
        urm[nvf] = lst[x];
        lst[x] = nvf;
    }

    for(int i = 1; i <= n; i++)
        if(!ok[i])
            df(i);

    for(int i = nrez; i >= 1; i--)
        out << rez[i] << ' ';
    out << '\n';
    return 0;
}