Cod sursa(job #920259)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 20 martie 2013 09:50:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 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();

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()
{
    int i,j;
    lista *p;
    for(i=1; i <=n; i++)
        if(grad[i]==0)
        {
            printf("%d ",i);
            grad[i]=-1;
            ns++;
            p=a[i];
            for(p=a[i]; p; p=p->next)
                grad[p->val]--;
            i=1;
        }
}