Cod sursa(job #671075)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 30 ianuarie 2012 17:37:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
using namespace std;
#define nd 50005
struct nod{int val; nod *urm; }*p[nd];
int n,m,grad[nd],dq[nd];
inline void readData()
{ nod *aux;
  int i,x,y;
freopen("sortaret.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d\n",&x,&y); ++grad[x];
    aux=new nod; aux->val=x; aux->urm=p[y]; p[y]=aux;
    }
}
void solveProblem()
{ int pr,u,i;
  nod *aux;
pr=1;u=0;
for(i=1;i<=n;++i)
    if(grad[i]==0)dq[++u]=i;
while(pr<=u)
    {
    aux=p[dq[pr]];
    while(aux!=NULL)
        {
        if(--grad[aux->val]==0)dq[++u]=aux->val;
        aux=aux->urm;
        }
    pr++;
    }
}
inline void writeData()
{ int i;
freopen("sortaret.out","w",stdout);
for(i=n;i>=1;--i)
    printf("%d ",dq[i]);
fclose(stdout);
}
int main()
{
readData();
solveProblem();
writeData();
return 0;
}