Cod sursa(job #463055)

Utilizator giuliastefGiulia Stef giuliastef Data 14 iunie 2010 14:29:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#define ALB 0
#define GRI 1
#define NEGRU 2
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
struct nod{
       int info;
       nod *next;
       } *vecini[50005],*ordine;
int n,m,color[50005];
void add(nod *&prim,int val)
{
     nod *p=new nod;
     p->info=val;
     p->next=prim;
     prim=p;
}
void push(int nodul)
{
     nod *p=new nod;
     p->info=nodul;
     p->next=ordine;
     ordine=p;
}
void citire()
{
     int i,x,y;
     f>>n>>m;
     for(i=1;i<=m;i++)
     {
                      f>>x>>y;
                      add(vecini[x],y);
     }
     f.close();
}
void dfs(int nodul)
{
     nod *p;
     color[nodul]=GRI;
     for(p=vecini[nodul];p;p=p->next)
      if(color[p->info]==ALB)
       dfs(p->info);
      color[nodul]=NEGRU;
      push(nodul);
}
void sortare_topologica()
{
     int i;
     for(i=1;i<=n;i++)
      if(color[i]==ALB)
       dfs(i);
}
void afisare()
{
     nod *p;
     for(p=ordine;p;p=p->next)
      g<<p->info<<" ";
     g<<"\n";
     g.close();
}
int main()
{
    citire();
    sortare_topologica();
    afisare();
    return 0;
}