Cod sursa(job #2807109)

Utilizator Zamolxis25Sebastian Gradinaru Zamolxis25 Data 23 noiembrie 2021 13:39:51
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

class Graf{
private:
    int nrNoduri;
    int nrMuchii;
    bool isOrientat;
    vector<vector<int>> listeAdiacenta;

public:
    Graf(int m_nrNoduri, int m_nrMuchii, bool m_isOrientat, vector<vector<int>> &m_listeAdiancenta){
        nrNoduri = m_nrNoduri;
        nrMuchii = m_nrMuchii;
        isOrientat = m_isOrientat;
        listeAdiacenta.resize(nrNoduri+1);
        for(int i = 1; i <= nrNoduri; i++){
            for(int j = 0; j < m_listeAdiancenta[i].size(); j++){
                listeAdiacenta[i].push_back(m_listeAdiancenta[i][j]);
            }
        }
    }

    void test(){
        cout<< nrNoduri << " " << nrMuchii <<'\n';
        for(int i = 1; i <= nrNoduri; i++){
            cout<<i<<": ";
            for(int j : listeAdiacenta[i]){
                cout<<j<<", ";
            }
            cout<<'\n';
        }
    }

    int dfsTop(int idx, int i, bool isVisited[100001], int sortat[100001]){
        isVisited[i] = true;

        for(int vecin : listeAdiacenta[i]){
            if(!isVisited[vecin]){
                idx = dfsTop(idx, vecin, isVisited, sortat);
            }
        }

        sortat[idx] = i;
        return idx - 1;
    }

    void topSort(){
         bool isVisited[100001] = {false};
         int idx = nrNoduri - 1;
         int sortat[100001];

         for(int i = 0; i < nrNoduri; i++){
             if(!isVisited[i]){
                 idx = dfsTop(idx, i, isVisited, sortat);
             }
         }

         for(int i = 0; i < nrNoduri; i++){
             fout<<sortat[i]<<" ";
         }
    }
};

int n, m, from, to;
vector<vector<int>> la;

int main() {

    fin>>n>>m;

    la.resize(n+1);
    for(int i = 0; i < m; i++){
        fin>>from>>to;
        la[from].push_back(to);
    }
    Graf graf = Graf(n, m, true, la);
    //graf.test();
    graf.topSort();
    return 0;
}