Cod sursa(job #175820)

Utilizator frEak-Calin Paul frEak- Data 10 aprilie 2008 14:18:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>   
typedef struct nod {  
        int vf;  
        nod * next;  
} *PNOD, NOD;  
PNOD vecini[50013]; 
PNOD adresa;
int viz[50013];//0-nevizitat, 1-in vizita, 2-vizitat  
int n,m; 

void adauga(int i,int j)  
{  
  PNOD p=new NOD;  
  p->vf=j;  
  p->next=vecini[i];  
  vecini[i]=p;  
}  
void citire()  
{
  freopen("sortaret.in","r",stdin);  
  scanf("%d %d",&n,&m);  
  int x,y;  
  for (int i=0;i<m;i++)  
  {  
    scanf("%d%d",&x,&y);  
    adauga(x,y);  
  };
  fclose(stdin);
}  
void push( int nod )  
{  
  PNOD p=new NOD;  
  p->vf=nod;  
  p->next=adresa;  
  adresa=p;  
}

void dfs( int nod )  
{  
  viz[nod]=1;  
  for (PNOD p=vecini[nod];p;p=p->next)  
    if (viz[p->vf]==0) dfs(p->vf );  
  viz[nod]=2;  
  push(nod);  
}

int main()  
{  
  citire(); 
  for (int i=1;i<=n;i++)  
    if (viz[i]==0) dfs(i);  

  freopen("sortaret.out","w",stdout);  
  for (PNOD p=adresa;p;p=p->next)  
  printf("%d ",p->vf);     
  return 0;  
}