Cod sursa(job #204499)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 24 august 2008 18:07:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <list>
#include <cstdio>
#define N 50001
#define M 100001
using namespace std;
typedef list<long>::iterator itl;

struct sm{long nod,urm;}muc[M];
long p[N],vf;
long in[N];
list<long> l;

void adauga(long a, long b)
{muc[++vf].urm=p[a];
 p[a]=vf;
 muc[vf].nod=b;
}
void adauga_vecini(long u)
{long i;
 for (i=p[u];i;i=muc[i].urm)
 {l.push_back(muc[i].nod);
 }
}

int main ()
{FILE *fin=fopen("sortaret.in","r");
 FILE *fout=fopen("sortare.out","w");
 long n,m,i,a,b,it1;
 itl it,it2;
 fscanf(fin,"%ld%ld",&n,&m);
 for (i=1;i<=m;i++)
 {fscanf(fin,"%ld%ld",&a,&b);
  adauga(a,b);
  in[b]++;
 }
 for (i=1;i<=n;i++)
 {if(in[i]==0)
  {break;}
 }
 adauga_vecini(i);
 fprintf(fout,"%ld ",i);
 for (it=l.begin();it!=l.end();)
  {it1=*it;
   if(in[*it]<=1)
   {fprintf(fout,"%ld ",*it);
    adauga_vecini(*it);
    it2=it;it2++;
    l.erase(it);
    it=it2;
   }
   else
   {in[*it]--;
    ++it;
  }
 }


 
 fclose(fout);
 return 0;
}