Cod sursa(job #905645)

Utilizator AndreiTeodorAndrei R AndreiTeodor Data 5 martie 2013 23:51:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 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],afisat[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)
    {
        if(!afisat[w])
        {
            sol[++k] = w;
            afisat[w] = 1;
        }
    }
    else
    {
        p = graph[w];
        while(p)
        {
            ex[w]--;
            if(!afisat[p->value])
                Parcurge(p->value);
            p=p->next;
        }
        Parcurge(w);
    }
}

int main()
{
    Read();

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

    Write();
    return 0;
}