Cod sursa(job #772201)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 28 iulie 2012 18:47:58
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
/* sortare topologica */

#include<fstream>
#include<stdio.h>
using namespace std;
#define alb 0
#define gri 1
#define negru 2

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

struct lista {int node; lista* next;};
lista* a[100005];   //lista vecini pt fiecare nod
lista* head;   //lista simplu inlantuita

int n,m,i,color[50005];

void add(int x, int y)
{lista* q=new lista;
 q->node=y;
 q->next=a[x];
 a[x]=q;} 
 
void depth (int x)
{color[x]=gri;
 lista* q=a[x];
 while(q)
 {if(color[q->node]==alb)
      depth(q->node);
 q=q->next;}
 color[x]=negru;
 lista* list_element=new lista;
 list_element->node=x;
 list_element->next=head;
 head=list_element; 
}  

int main()
{f>>n>>m;
int x,y;
for(i=1; i<=m; i++)
  {f>>x>>y;
   add(x,y);}

for(i=1; i<=n; i++)
  if(color[i]==alb)
    depth(i);

lista* q = head;
while(q)
{g<<q->node<<" ";
 q=q->next;}   
f.close();
g.close();    
return 0;}