Cod sursa(job #920146)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 20 martie 2013 08:45:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.56 kb
#include <cstdio>

using namespace std;

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

class lista
{
    public:
        element *start;
        element *last;
        int n;

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

    int & operator [] (int x)
    {
        element *p=start;
        for(int i=0;i<x;i++)
            p=p->next;
        return p->val;
    }

    void push_front(int x)
    {
        if(n)
        {
            start->prev=new element;
            start->prev->next=start;
            start=start->prev;
        }
        start->val=x;
        n++;
    }

    void push_back(int x)
    {
        if(n)
        {
            last->next=new element;
            last->next->prev=last;
            last=last->next;
        }
        last->val=x;
        n++;
    }

    void erase(int x)
    {
        if (n==0)
            return;
        if(n==1)
        {

            n--;
            return;
        }
        element *p=start;
        for(int i=0;i<x;i++)
            p=p->next;
        if(p==start&&p==last)

        if(p!=last)
            p->next->prev = p->prev;
        if(p!=start)
            p->prev->next = p->next;
        delete p;
        n--;
    }

    void insert(int poz, int x)
    {
        if(poz==0)
        {
            push_front(x);
            return;
        }
        if(poz==n)
        {
            push_back(x);
            return;
        }
        element *p=start;
        element *nou=new element;
        nou->val=x;
        for(int i=0;i<poz;i++)
            p=p->next;
        p->prev->next=nou;
        nou->prev=p->prev;
        p->prev=nou;
        nou->next=p;
        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=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        grad[y]++;
        a[x].push_back(y);
    }
}

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