Cod sursa(job #2130086)

Utilizator ioana_pelinIoana Pelin ioana_pelin Data 13 februarie 2018 13:47:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>

#include <vector>

using namespace std;

ifstream fin("sortaret.in");

ofstream fout("sortaret.out");

vector <int> L[50005];

vector <int> gi(50005);

vector <int> niv(50005);

int n, m;

void citire();

void descompunere();



int main()

{

    citire();

    descompunere();

    return 0;

}



void citire()

{

    int i,x,y;

    fin>>n>>m;

    for(i=1; i<=m; i++)

    {

        fin>>x>>y;

        L[x].push_back(y);

        gi[y]++;

    }

}

void descompunere()

{

    int i,j,nr=0,nrniv=0;

    while(nr<n)

    {

        ++nrniv;

        for(i=1; i<=n; i++)

            if(!gi[i])

            {

                niv[i]=nrniv;

                fout<<i<<" ";

                nr++;

            }



        for(i=1; i<=n; i++)

           if(niv[i]==nrniv)

            {

                gi[i]=-1;

                for(j=0; j<L[i].size(); j++) gi[L[i][j]]--;

            }

    }

}