Cod sursa(job #920298)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 20 martie 2013 10:20:15
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>

using namespace std;

struct lista
{
    lista *next;
    int val;
};

int n,m,ns;
lista *a[50010];
int grad[50010];

void push(int l, int x)
{
    lista *p= new lista;
    p->val=x;
    p->next = a[l];
    a[l]=p;
}

void citire();
void rezolvare();
void df(int i);

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    citire();
    rezolvare();
    return 0;
}

void citire()
{
    int x,y,i,j,nr;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        grad[y]++;
        bool ad=true;
        for(lista *p=a[x]; p; p = p->next)
            if(p->val==y)
            {
                ad=false;
                break;
            }
        if(ad)
            push(x,y);
    }
}

void rezolvare()
{
    for(int i=1; i <=n; i++)
        if(grad[i]==0)
            df(i);
    for(int i=1; i <=n; i++)
        if(grad[i]==0)
            printf("%d ",i);
}

void df(int i)
{
    printf("%d ",i);
    grad[i]=-1;
    ns++;
    lista *p;
    p=a[i];
    for(p=a[i]; p; p=p->next)
    {
        grad[p->val]--;
        if(grad[p->val]==0)
            df(p->val);
    }
}