Cod sursa(job #2133826)

Utilizator liaamzaLiA Amza liaamza Data 17 februarie 2018 12:52:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <queue>
using namespace std;

#define MAXN 50000

int N, M, gradeIn[MAXN+1];
queue<int> succesori[MAXN+1], coadaNoduriDeGrad0;
 #define getCoada(el, c) {\
    el=c.front();\
    c.pop();\
 }
void citire(void)
{
    int i, a, b;
    ifstream fin("sortaret.in", ios::in);
    fin>>N>>M;
    for(i = 1; i <= M; i++)
    {
        fin>>a>>b;
        succesori[a].push(b);
        gradeIn[b]++;
    }
    fin.close();
}

void calcul(void)
{
    ofstream fout("sortaret.out", ios::out);
    int i, x, vecinul;

    for(x = 1; x <= N; x++)
    {
        if( !gradeIn[x])
            coadaNoduriDeGrad0.push(x);
    }

    for(i = 1; i <= N; i++)
    {
        getCoada(x, coadaNoduriDeGrad0);
        //x = coadaNoduriDeGrad0.front();
        //coadaNoduriDeGrad0.pop();
        fout<<x<<" ";
       while(!succesori[x].empty())
        {
            getCoada(vecinul, succesori[x]);
            //vecinul=succesori[x].front();
            //succesori[x].pop();
            gradeIn[vecinul]--;
            if(gradeIn[vecinul] == 0)
            {
                coadaNoduriDeGrad0.push(vecinul);
            }
        }
    }
    fout<<endl;
    fout.close();
}

int main(void)
{
    citire();
    calcul();
    return 0;
}