Cod sursa(job #349677)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 21 septembrie 2009 09:20:12
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<stdio.h>
#define DIM 100005
struct graf
{
       int x;
       graf *urm;
} *lst[DIM];
int n,m,c[DIM],gr[DIM];
void add (int a,int b)
{
    graf *p=new graf;
    p->x=b;
    p->urm=lst[a];
    lst[a]=p;
}
void read ()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        ++gr[y];
    }
}
void solve ()
{
    int st=1,dr=0;
    for(int i=1;i<=n;++i)
        if(!gr[i])
            c[++dr]=i;
    graf *p;
    while(st<=dr)
    {
        printf("%d",c[st]);
        for(p=lst[c[st]];p;p=p->urm)
            if(--gr[p->x]==0)
                c[++dr]=p->x;
        ++st;
    }
}
int main ()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    read ();
    solve ();
    return 0; 
}