Cod sursa(job #2419968)

Utilizator Marius92roMarius Marius92ro Data 9 mai 2019 22:53:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 100005

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int nrNoduri, nrMuchii;
vector <int> lista[NMAX];
vector <int> grafTranspus[NMAX];
queue <int> sortare;
bool vizitat[NMAX];
int grade[NMAX];

void dfs(int nodStart){

    vizitat[nodStart] = true;

    int nrVecini = lista[nodStart].size();

    for ( int vecin = 0; vecin < nrVecini; vecin++){
                if ( !vizitat[lista[nodStart][vecin]] )
                       dfs(lista[nodStart][vecin]);
    }

    fout << nodStart << " ";

}

void sortareTopologica(){

    while ( !sortare.empty() ){

        int nodCurent  = sortare.front();

        for ( int vecin = 0; vecin < grafTranspus[nodCurent].size(); vecin++ ){

            grade[grafTranspus[nodCurent][vecin]]--;

            if ( grade[grafTranspus[nodCurent][vecin]] == 0 )
                    sortare.push(grafTranspus[nodCurent][vecin]);


        }

        fout << nodCurent << " ";

        sortare.pop();

    }

}

int main(){

    if ( !fin ){
        cout << "\nEroare la deschiderea fisierului !\n";
       // exit(-1);
    }

    fin >> nrNoduri >> nrMuchii;

    for ( int i = 1; i <= nrNoduri; i++){
                    vizitat[i] = false;
                    grade[i] = 0;
    }

    for ( int i = 1; i <= nrMuchii; i++){
            int x,y;
            fin >> x >> y;
            lista[y].push_back(x);
           // grafTranspus[j].push_back(i);
          //  grade[i]++;
    }


  //  for ( int i =1; i <= nrNoduri; i++)
      //  if ( grade[i] == 0 )
               // sortare.push(i);

  //  sortareTopologica();

    for ( int i = 1; i <= nrNoduri; i++)
        if ( !vizitat[i] )
                    dfs(i);

    return 0;

}