Cod sursa(job #2133796)

Utilizator liaamzaLiA Amza liaamza Data 17 februarie 2018 12:12:53
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <queue>
#include<set>
//#define DEPANARE
using namespace std;
#define MAXN 50000
int n, m;
typedef queue<unsigned short int> CoadaDeIntregi;
typedef set<unsigned short int> Multime;
CoadaDeIntregi cSortata;
typedef CoadaDeIntregi CoziDeIntregi[MAXN+1];
CoziDeIntregi succesori;
unsigned short int gradIntrare[MAXN+1];
Multime noduriDeGradInterior0;
void citire(void)
{
    ifstream fin("sortaret.in", ios::in);
    fin>>n>>m;
    unsigned short int i,x,y;
    for(i=1;i<=n;i++)
    {
        noduriDeGradInterior0.insert(i); //presupunem ca toate elementele ar fi de grad 0
    }
    for(i=0;i<m;i++)
    {
        fin>>x>>y;
        gradIntrare[y]++;
        succesori[x].push(y);
        noduriDeGradInterior0.erase(y);
    }
    fin.close();
}

void calcul(void)
{
    unsigned short int x=0, y=0;
    while(!noduriDeGradInterior0.empty())
    {
        x= *(noduriDeGradInterior0.begin());
        noduriDeGradInterior0.erase(x);
        cSortata.push(x);
        while(!succesori[x].empty())
        {
            y=succesori[x].front();
            succesori[x].pop();
            if( ! (--gradIntrare[y]) ) //a ajuns 0?
            {
                noduriDeGradInterior0.insert(y);
            }
        }
    }
}

void scrieSolutia(void)
{
    ofstream fout("sortaret.out", ios::out);
    while(!cSortata.empty())
    {
        fout<<cSortata.front()<<" ";
        cSortata.pop();
    }
    fout<<endl;
    fout.close();
}
int main()
{
    bool vecheaValoare=cin.sync_with_stdio(false);

    citire();
#ifdef DEPANARE
    cout<<sizeof(cSortata)<<endl;
    cout<<sizeof(succesori)<<endl;
    cout<<sizeof(gradIntrare)<<endl;
    cout<<sizeof(noduriDeGradInterior0)<<endl;
#endif
    //cout<<"multimea de succesori ocupa"<<sizeof(succesori)<<endl;
    //cout<<sizeof(queue<int>)<<endl;
    calcul();
    //cout<<sizeof(cSortata)<<endl;
    scrieSolutia();
    cin.sync_with_stdio(vecheaValoare);
    return 0;
}