Cod sursa(job #905638)

Utilizator AndreiTeodorAndrei R AndreiTeodor Data 5 martie 2013 23:32:00
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;

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

const int maxn = 50001;
int n,m,k;
int sol[maxn],ex[maxn];

struct Nod
{
    int value;
    Nod*next;
}*graph[maxn],*q;

void Read()
{
    int i,a1,a2;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a1>>a2;

        q = new Nod;
        q->value = a2;
        q->next = graph[a1];
        graph[a1] = q;

        ex[a1]++;
    }
}

void Write()
{
    for(int i=n;i>=1;i--)
        g<<sol[i]<<' ';
}

void Parcurge(int w)
{
    Nod*p;

    if(ex[w]==0)
        sol[++k] = w;
    else
    {
        p = graph[w];
        while(p)
        {
            ex[w]--;
            Parcurge(p->value);
            p=p->next;
        }
        Parcurge(w);
    }
}

int main()
{
    Read();

    for(int i=1;i<=n;i++)
        Parcurge(i);

    Write();
    return 0;
}