Cod sursa(job #995556)

Utilizator tiger13mkLucian-Hoffmann Monica tiger13mk Data 9 septembrie 2013 13:18:31
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>

#define ALB 0
#define GRI 1
#define NEGRU 2
#define NMAX 50005

using namespace std;

struct nod
{
    int vf;
    nod *next;
};

nod *l[NMAX],*adresa;
int color[NMAX],n,m;

void add(int i,int j)
{
    nod *p=new nod;
    p->vf=j;
    p->next=l[i];
    l[i]=p;
}

void citire()
{
    ifstream f("sortaret.in");
    f>>m>>n;
    int x,y;
    for(;m>0;m--)
    {
        f>>x>>y;
        add(x,y);
    }
}

void push(int inod)
{
    nod *p=new nod;
    p->vf=inod;
    p->next=adresa;
    adresa=p;
}

void DF(int inod)
{
    color[inod]=GRI;
    for(nod *p=l[inod];p;p=p->next)
        if(color[p->vf]==ALB)
            DF(p->vf);
    color[inod]=NEGRU;
    push(inod);
}

void sort_top()
{
    int i;
    for(i=1;i<=n;i++)
        if(color[i]==ALB)
            DF(i);
}

void afisare()
{
    ofstream g("sortaret.out");
    for(nod *p=adresa;p;p=p->next)
        g<<p->vf<<" ";
}

int main()
{
    citire();
    sort_top();
    afisare();
    return 0;
}