Cod sursa(job #1205237)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 5 iulie 2014 19:02:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
using namespace std;
struct nod
{int inf;
 nod *nx;
} *x[50000];
int c[50000],cv[50000];
int M,N;
void add(int i,int j)
{
 cv[j]++;
nod *c=x[i];
 nod *d=new nod;
 d->nx=NULL;
 d->inf=j;
 if(c==NULL)
    x[i]=d;
 else
  {while(c->nx)
      c=c->nx;
   c->nx=d;
  }
}
void akk(int b)
{nod *c=x[b];
 while(c)
 {cv[c->inf]--;
  c=c->nx;
 }
}
void Solve()
{int s,f;
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
 scanf("%d%d",&N,&M);
 while(M)
 {scanf("%d%d",&s,&f);
  add(s,f);
  M--;
 }
 int k,v,m=N,j;
 do
 {k=1;
  v=0;
  for(j=1;j<=N;j++)
    if(cv[j]==0)
     {v=1;
      c[k]=j;
      k++;
      m--;
      cv[j]=-1;
     }
  for(j=1;j<k;j++)
  {akk(c[j]);
   printf("%d ",c[j]);
  }
 }
 while(v&&m);
}
int main()
{
 Solve();
 return 0;
}