Cod sursa(job #2713424)

Utilizator MateGMGozner Mate MateGM Data 27 februarie 2021 21:36:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream be("sortaret.in");
ofstream ki("sortaret.out");

void beolvas(vector<vector<int>> &graf,int n, int m);
void topo_rendezes(const vector<vector<int>> &graf, int n);
void DFS(const vector<vector<int>> &graf, vector<bool> &latogatott,vector<int> &topo_sorrend,int kezdo);

int main(){
    int n, m;
    be >> n >> m;
    vector<vector<int>> graf(n);
    beolvas(graf, n, m);
    topo_rendezes(graf, n);   
}

void beolvas(vector<vector<int>>& graf, int n, int m) {
    for (int i = 0; i < m; i++) {
        int x, y;
        be >> x >> y;
        graf[x - 1].push_back(y - 1);
    }
}

void topo_rendezes(const vector<vector<int>> &graf, int n) {
    vector<bool> latogatott(n, false);
    vector<int> topo_sorrend;

    for (int i = 0; i < n; i++) 
        if (!latogatott[i]) DFS(graf, latogatott, topo_sorrend, i);

    for (int i = topo_sorrend.size() - 1; i >= 0; i--)
        ki << topo_sorrend[i] + 1 << " ";
}

void DFS(const vector<vector<int>> &graf, vector<bool>& latogatott, vector<int>& topo_sorrend, int kezdo) {
    latogatott[kezdo] = true;

    for (int i : graf[kezdo])
        if (!latogatott[i]) DFS(graf, latogatott, topo_sorrend, i);

    topo_sorrend.push_back(kezdo);
}