Cod sursa(job #1610729)

Utilizator NicusorTelescu Nicolae Nicusor Data 23 februarie 2016 18:22:46
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <queue>

using namespace std;

queue <int> q;

struct nod
{
    int arc;
    nod *urm;
};

int gr_intrare[50001];
nod *v[50001],*v1[50001];

bool introdus(int a,int b)
{
    nod *k;
    k=v[a];
    while (k)
    {
        if (k->arc==b)
            return 1;
        k=k->urm;
    }
    return 0;
}

void goleste(int x)
{
    nod *k;
    k=v[x];
    while (k)
    {
        gr_intrare[k->arc]--;
        if (gr_intrare[k->arc]==0)
        {
            printf("%d ",k->arc);
            goleste(k->arc);
        }
        k=k->urm;
    }
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d %d\n",&a,&b);
        if (v[a]==NULL)
        {
            nod *p;
            p=new nod;
            p->arc=b;
            p->urm=NULL;
            v[a]=p;
            v1[a]=p;
            gr_intrare[b]++;
        }
        else
        {
            if (!introdus(a,b))
            {
                nod *p;
                p=new nod;
                p->arc=b;
                p->urm=NULL;
                v1[a]->urm=p;
                v1[a]=p;
                gr_intrare[b]++;
            }
        }
    }
    int coada[50001];
    coada[0]=0;
    for (int i=1;i<=n;i++)
    {
        if (gr_intrare[i]==0)
        {
            coada[0]++;
            coada[coada[0]]=i;
        }
    }
    for (int i=1;i<=coada[0];i++)
    {
        printf("%d ",coada[i]);
        goleste(coada[i]);
    }
}