Cod sursa(job #920211)

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

using namespace std;

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

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

void push(lista &l, int x)
{
    element *p= new element;
    p->val=x;
    if(l.n)
        p->next = l.start;

    l.start=p;
    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]--;
            }
    }
}