Cod sursa(job #920182)

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

using namespace std;

struct element
{
    element *next, *prev;
    int val;
};

struct lista
{
    element *start;
    element *last;
    int n;

    lista()
    {
        n=0;
        start=new element;
        last=start;
    }
};

void push(lista &l, int x)
{
    if(l.n)
    {
        l.last->next=new element;
        l.last->next->prev=l.last;
        l.last=l.last->next;
    }
    l.last->val=x;
    l.n++;
}


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

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]++;
        element *p=a[x].start;
        bool ad=true;
        for(j=0;j<a[x].n;j++, p=p->next)
            if(p->val==y)
            {
                ad=false;
                break;
            }
        if(ad)
            push(a[x],y);
    }
}

void rezolvare()
{
    int i,j;
    element *p;
    while(ns<m)
    {
        for(i=1; i <=n; i++)
            if(grad[i]==0)
            {
                printf("%d ",i);
                grad[i]=-1;
                ns++;
                p=a[i].start;
                for(j = 0; j < a[i].n; j++, p=p->next)
                    grad[p->val]--;
            }
    }
}