Cod sursa(job #1417537)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 10 aprilie 2015 15:19:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#define ALB 0
#define GRI 1
#define NEGRU 2
#define NMAX 50005
using namespace std;
typedef struct nod
{
    int vf;
    nod * next;
}*PNOD,NOD;
PNOD L[NMAX];
PNOD adresa;
int color[NMAX];
int N, M;
void Read();
void DF(int);
void Push(int);
void S_Topologica();
void Add( int,int);
void Write();
int main()
{
    Read();
    S_Topologica();
    Write();
    return 0;
}
void Read()
{
     ifstream f("sortaret.in");
     f>>N>>M;
     int X,Y;
     for(;M>0;M--)
     {
         f>>X>>Y;
         Add(X,Y);
     }
}
void Add(int i,int j)
{
     PNOD p=new NOD;
     p->vf=j;
     p->next=L[i];
     L[i]=p;
}
void S_Topologica()
{
    int i;
    for(i=1;i<=N;++i)
      if(color[i]==ALB)
        DF(i);
}
void DF(int nod)
{
    color[nod]=GRI;
    for(PNOD p=L[nod];p;p=p->next)
      if(color[p->vf]==ALB)
        DF(p->vf);
     color[nod]=NEGRU;
     Push(nod);
}
void Push(int nod)
{
     PNOD p=new NOD;
     p->vf=nod;
     p->next=adresa;
     adresa=p;
}
void Write()
{
     ofstream g("sortaret.out");
     for(PNOD p=adresa;p;p=p->next)
         g<<p->vf<<" ";
}