Cod sursa(job #772170)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 28 iulie 2012 16:13:12
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
/* sortare topologica */

#include<fstream>
using namespace std;

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

int n,m,i,j,queue[50001],viz[50001],end,beg;
int incoming[50001];
struct edge{int node; edge* next;};
edge* a[100001];

void add(int x, int y)
{edge* q=new edge;
 q->node=y;
 q->next=a[x];
 a[x]=q;}

//struct lista{int nod; lista* next};
//lista* head;

int main()
{f>>n>>m;
int x,y;
for(i=1; i<=m; i++)
  {f>>x>>y;
   add(x,y);
   incoming[y]++;}
end=0;   
for(i=1; i<=n; i++)
  if(incoming[i]==0)
   {end++;
    queue[end]=i;
    viz[i]=1;}
beg=1;
while(end<=n-1)
{edge* q = a[beg];
 while(q)
   if(viz[q->node]==0)
   {incoming[q->node]--;
    if(incoming[q->node]==0)
      {end++;
       queue[end]=q->node;
       viz[q->node]=1;}
    q=q->next;
    } 
beg++;}   

for(i=1; i<=end; i++)
g<<queue[i]<<" ";     
f.close();
g.close();    
return 0;}