Cod sursa(job #2919294)

Utilizator utilizator20052022utilizatorr utilizator20052022 Data 16 august 2022 17:25:26
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include<fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

class Graph{
private:
    int n_nodes;
    vector<vector<int>> adj;
    vector<pair< int , pair<int,int>> > adj_weight;
public:
    Graph(){
        n_nodes = 0;
        adj = {};
    }
    Graph(int n, vector<vector<int>> &gr){
        n_nodes = n;
        adj = gr;
    }

    void dfs_ctc(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution);
    void solve_sort_top();
};

void Graph:: dfs_ctc(int node, vector<bool> &visited, vector<vector<int>> &gr, vector<int> &solution){
    visited[node] = true;
    for(auto &x: gr[node]){
        if(!visited[x]) dfs_ctc(x, visited, gr, solution);
    }
    solution.push_back(node);
}

void Graph::solve_sort_top(){
    vector<bool> v(n_nodes+1, false);
    vector<int> sol(n_nodes+1);
    for(int i = 1; i <= n_nodes; ++i){
        if(!v[i]) dfs_ctc(i, v, adj, sol);
    }
    reverse(sol.begin(), sol.end());
    for(int i = 0; i < n_nodes; ++i)
        //cout<<sol[i]<<' ';
        fout<<sol[i]<<' ';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, x, y;
   // cin>>n>>m;
    fin>>n>>m;
    vector<vector<int>> aux(n+1);
    for(int i = 0; i < m; ++i){
       // cin>>x>>y;
        fin>>x>>y;
        aux[x].push_back(y);
    }

    Graph g = Graph(n, aux);
    g.solve_sort_top();
    return 0;
}