Cod sursa(job #1701901)

Utilizator mariakKapros Maria mariak Data 14 mai 2016 12:44:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
#define Nmax 50002
#define Mmax 100002

FILE *fin  = freopen("sortaret.in", "r", stdin);
FILE *fout = freopen("sortaret.out", "w", stdout);

using namespace std;
int n, m, vf[Mmax], Prev[Mmax], lst[Nmax], sol[Nmax], viz[Nmax];
void add(int x, int y)
{
    vf[++ vf[0]] = y;
    Prev[vf[0]] = lst[x];
    lst[x] = vf[0];
}
void read()
{
    int x, y;
    scanf("%d %d", &n, &m);
    while(m --)
    {
        scanf("%d %d", &x, &y);
        add(x, y);
    }
}
void DFS(int vert)
{
    viz[vert] = 1;
    int y = lst[vert];
    while(y)
    {
        if(!viz[vf[y]])
            DFS(vf[y]);
        y = Prev[y];
    }
    sol[++ sol[0]] = vert;
}
void solve()
{
    for(int i = 1; i <= n; ++ i)
        if(!viz[i])
            DFS(i);
}
void write()
{
    for(int i = sol[0]; i >= 1; -- i)
        printf("%d ", sol[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}