Cod sursa(job #2133737)

Utilizator liaamzaLiA Amza liaamza Data 17 februarie 2018 11:21:46
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <queue>
#include<set>
using namespace std;
#define MAXN 50000
#define MAXM 100000
//char arce[MAXN+1][MAXN+1];
int n, m;
typedef queue<int> CoadaDeIntregi;
typedef set<int> Multime;
CoadaDeIntregi cSortata;
typedef CoadaDeIntregi CoziDeIntregi[MAXN+1];
CoziDeIntregi succesori;
int gradIntrare[MAXN+1];
Multime noduriDeGradInterior0;
void citire(void)
{
    ifstream fin("sortaret.in", ios::in);
    fin>>n>>m;
    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;
        //if(!arce[x][y])
        {
         //   arce[x][y]=1;
            gradIntrare[y]++;
            succesori[x].push(y);
            noduriDeGradInterior0.erase(y);
        }
    }
    fin.close();
}

void calcul(void)
{
    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();
    calcul();
    scrieSolutia();
    cin.sync_with_stdio(vecheaValoare);
    return 0;
}