Cod sursa(job #671459)

Utilizator handz.FMI Andrei Tanasescu handz. Data 31 ianuarie 2012 15:30:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#define maxN 50005
#define maxM 100005
using namespace std;

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

int n,m,saw[maxN],st[maxN],nr=0;

struct graf
{
    int nod;
    graf *next;
} *G[maxM];

void addN(int x,int y)
{
    graf *p;
    p=new graf;
    p->nod=y;
    p->next=G[x];
    G[x]=p;
}

void read_ini()
{
    f>>n; f>>m;
    int i,a,b;
    for(i=1; i<=m ;i++)
    {
        f>>a; f>>b;
        addN(a,b);
    }
    for(i=1; i<=n ;i++)
        saw[i]=0;
}

void DF(int s)
{
    graf *q;
    saw[s]=1;
    for(q=G[s]; q!=NULL ;q=q->next)
    {
        if(!saw[q->nod])
            DF(q->nod);
    }
    st[nr++]=s;
}

int main()
{
    int i;
    read_ini();
    for(i=1; i<=n ;i++)
    {
        if(!saw[i])
            DF(i);
    }
    for(i=n-1; i>=0 ;i--)
        g<<st[i]<<" ";
    return 0;
}