Cod sursa(job #1498775)

Utilizator ilinoiuflaviusIlinoiu Flavius ilinoiuflavius Data 9 octombrie 2015 09:31:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#define nmax 50001
using namespace std;

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

struct nod
{
    int nr;
    nod *p;
}v[nmax];

int viz[nmax],n,m,pre[nmax],nr;


void DFS(int x)
{
    viz[x]=1;
    for(nod*q = &v[x]; q!=NULL; q=q->p)
    {
        if(!viz[q->nr])
            DFS(q->nr);

    }
    pre[++nr]=x;
}
inline void add(int a, int b)
{
    nod *q = new nod;
    q->nr = b;
    q->p = v[a].p;
    v[a].p=q;
}
inline void read()
{
    f>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        add(a,b);
    }
}
inline void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
            DFS(i);
    }
}
inline void write()
{
    for(int i=nr;i>=2;i--)
    {
        g<<pre[i]<<" ";
    }

}
int main()
{
    read();
    solve();
    write();
    return 0;
}