Cod sursa(job #2133848)

Utilizator liaamzaLiA Amza liaamza Data 17 februarie 2018 13:14:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include<iostream>
#include <queue>
using namespace std;

#define MAXN 50000

int N, M;
int *gradeIn;
queue<int> *succesori, 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;
    gradeIn=new int[MAXN+1];
    for(i=1;i<=N;i++)
    {
        gradeIn[i]=0;
    }
    succesori=new queue<int>[MAXN+1];
    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 x, vecinul;

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

    while(!coadaNoduriDeGrad0.empty())
    {
       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();
    delete gradeIn;
    delete succesori;
}

int main(void)
{
    bool vecheaValoare=istream::sync_with_stdio(false);
    citire();
    calcul();
    istream::sync_with_stdio(vecheaValoare);
    return 0;
}