Cod sursa(job #1711786)

Utilizator antanaAntonia Boca antana Data 1 iunie 2016 10:30:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#define MAXN 50000
#define MAXM 100000
using namespace std;
int k, r, lista[MAXN+1], next[2*MAXM+1], val[2*MAXM+1], nu[MAXN+1], viz[MAXN+1];
inline void adauga(int x, int y)
{
    val[++k]=y;
    next[k]=lista[x];
    lista[x]=k;
}
void dfs(int nod)
{
    int p=lista[nod];
    viz[nod]=1;
    while(p)
    {
        if(!viz[val[p]])
            dfs(val[p]);
        p=next[p];
    }
    nu[++r]=nod;
}
void afisare()
{
    int i;
    for(i=r;i>=1;i--)
        printf("%d ", nu[i]);
}
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m,x,y;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d", &x, &y);
        adauga(x, y);
    }
    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);
    afisare();
    return 0;
}