Cod sursa(job #728821)

Utilizator I.AlexandruIlie Alexandru I.Alexandru Data 28 martie 2012 23:51:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<fstream>
#define maxn 50005
using namespace std;

struct pnod{
int info;
pnod *next;
};

pnod *lv[maxn];
int n, x, y, st=0, viz[maxn], s[maxn];

void adauga(int x, int y)
{pnod *aux=new pnod;
aux->info=y;
aux->next=lv[x-1];
lv[x-1]=aux;
}

void df(int nod)
{viz[nod-1]=1;
for(pnod *aux=lv[nod-1]; aux; aux=aux->next)
   if(!viz[aux->info-1])
     df(aux->info);
s[st++]=nod;
}

void sortop()
{for(int i=0; i<n; i++)
    if(!viz[i]) 
      df(i+1);     
}

int main()
{ifstream f("sortaret.in");
ofstream g("sortaret.out");

f>>n>>x;

for(; f>>x>>y; )
   adauga(x, y);    

sortop();   
  
for(; st--;)
   g<<s[st]<<" ";   
        
return 0;    
}