Cod sursa(job #204690)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 26 august 2008 14:42:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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];
int f[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");
 //FILE *fbug=fopen("bug.txt","w");
 long n,m,i,a,b,it1;
 itl it,it2;
 fscanf(fin,"%ld%ld",&n,&m);
 //for (i=1;i<=n;i++){in[i]=-1;}

 for (i=1;i<=m;i++)
 {fscanf(fin,"%ld%ld",&a,&b);
  adauga(a,b);
  in[b]++;
  f[a]=1;f[b]=1;
 }
 
 for (i=1;i<=n;i++)
 {if(in[i]==0&&f[i]!=0)
  {l.push_back(i);
   //fprintf(fout,"%ld ",i);
  }
 }

 for (it=l.begin();it!=l.end();)
 {it1=*it;
  //fprintf(fbug,"%ld ",*it);
   if(in[*it]==1||in[*it]==0)
  {fprintf(fout,"%ld ",*it);
   adauga_vecini(*it);
   it2=it;it2++;
   l.erase(it);
   it=it2;
  }
  else
  {in[*it]--;
   ++it;
  }
 }


// fclose(fbug);
 fclose(fout);
 return 0;
}