Cod sursa(job #1610732)

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

using namespace std;

queue <int> q;

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

int gr_intrare[50001],solutie[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)
        {
            q.push(k->arc);
            solutie[0]++;
            solutie[solutie[0]]=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]++;
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (gr_intrare[i]==0)
        {
            q.push(i);
            solutie[0]++;
            solutie[solutie[0]]=i;
        }
    }
    while (!q.empty())
    {
        int x=q.front();
        printf("%d ",x);
        goleste(x);
        q.pop();
    }
}