Cod sursa(job #522743)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 15 ianuarie 2011 23:42:05
Problema Sortare topologica Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#define NR 50001
typedef struct Nod
{long info;
struct Nod *next;}nod,*list;
typedef struct
{list lad;
long grin;}head;
typedef head graf[NR];
graf g;
long n,i,j,k,m,c[NR],gasit;

void add(list &l,long x)
{nod *nou=new nod;
nou->info=x;
nou->next=l;
l=nou;}

int apartine(list l,long x)
{list c;
for(c=l;c!=NULL;c=c->next)
if(c->info==x)
         return 1;
return 0;}

void del(list &l,long x)
{nod *p=l,*q=l;
while(p!=NULL&&p->info!=x)
         {q=p;
         p=p->next;}
if(p!=NULL)
         {if(q==p)
                  l=l->next;
         else
                  q->next=p->next;
         free(p);}}

void delNod(graf g,long i)
{long j;
for(j=1;j<=n;j++)
if(apartine(g[j].lad,i)==1)
         {g[j].grin--;
         del(g[j].lad,i);}}

int main()
{fstream f1("sortaret.in",ios::in);
fstream f2("sortaret.out",ios::out);
f1>>n>>m;
for(i=1;i<=n;i++)
       {c[i]=0;
       g[i].lad=NULL;
       g[i].grin=0;}
for(k=1;k<=m;k++)
       {f1>>i>>j;
       if(apartine(g[j].lad,i)==0)
                {add(g[j].lad,i);
                g[j].grin++;}}
do
       {gasit=0;
       for(i=1;(i<=n)&&(gasit==0);i++)
       if(c[i]==0&&g[i].grin==0)
                {gasit=1;
                c[i]=1;
                f2<<i<<" ";
                delNod(g,i);}}
while(gasit);
f1.close();
f2.close();
return 0;}