Cod sursa(job #2798205)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 11 noiembrie 2021 00:04:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMax = 50001;
bool visited[NMax + 5];

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

class Graph
{
public:
    vector <int> g[NMax + 5];
    vector <int> solution;
    int n, m;

    void InsertInGraph();
    void DFS(int vf);
};


void Graph::InsertInGraph(){
    int n1, n2;

    fin >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        fin >> n1 >> n2;
        g[n1].push_back(n2);
    }
}


void Graph::DFS(int vf)
{
    visited[vf] = true;

    for (auto it: g[vf])
        if (!visited[it])
            DFS(it);

    solution.push_back(vf);
}


int main(){

    Graph G;

    G.InsertInGraph();

    for (int i = 1; i <= G.n; ++i)
        if (!visited[i])
            G.DFS(i);

    int upper_limit = G.solution.size() - 1;
    for (int i = upper_limit; i > -1; i--)
        gout << G.solution[i] << ' ';


    return 0;

}