Cod sursa(job #2792678)

Utilizator monicaandreea46Girbea Monica monicaandreea46 Data 2 noiembrie 2021 10:14:07
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
std::ifstream f("sortaret.in");
std::ofstream fg("sortaret.out");
int n, m, a, b;

class graf{
public:
    int n, m;

    graf(int n, int m);

    std::map<int, std::vector<int> > lista;
    std::vector<int> viz;
    std::deque<int> coada;

    void new_lista( int nod1, int nod2);
    void dfs(int nod);
    void sortare();

};

graf::graf(int n, int m) {
    this->n = n;
    this->m = m;
}

void graf::new_lista(int nod1, int nod2){
    lista[nod1].push_back(nod2);
    //lista[nod2].push_back(nod1);
}

void graf::dfs(int nod){
    static int cnt = 0;
    viz[nod] = ++cnt;

    for( auto i = lista[nod].begin(); i != lista[nod].end(); i++) {
        if (viz[*i] == -1) dfs(*i);
    }

    coada.push_back(nod);
}

void graf::sortare(){
    for(auto i = 0 ; i<=n ; i++){
        viz.push_back(-1);
    }

    for(int i = 0 ; i< n ; i++){
        if(viz[i] == -1) dfs(i);
    }

    /*for(int i=0 ; i<n ; i++)
        std::cout<<viz[i]<<" ";*/

    while(!coada.empty()){
        int aux = coada.back();
        fg<<aux + 1<<" ";
        coada.pop_back();
    }
}

int main() {
    f>>n>>m;

    graf g(n, m);
    for(int i=0 ; i<m ; i++){
        f>>a>>b;
        g.new_lista(a-1,b-1);
    }

    g.sortare();
    return 0;
}