Cod sursa(job #2591953)

Utilizator Horia14Horia Banciu Horia14 Data 31 martie 2020 18:43:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<iostream>
#include<vector>
#define MAX_VERTICES 50000
using namespace std;

class Graph {
private:
    int V;
    int E;
    vector<int> g[MAX_VERTICES + 1];
public:
    void readGraph(string name_fin) {
        int x, y;
        ifstream fin(name_fin);
        fin >> V >> E;
        for(int i = 0; i < E; ++i) {
            fin >> x >> y;
            g[x].push_back(y);
        }
        fin.close();
    }

    void DFS(int node, vector<bool>& isVisited, vector<int>& v) {
        isVisited[node] = true;
        for(auto i : g[node])
            if(!isVisited[i])
                DFS(i, isVisited, v);
        v.push_back(node);
    }

    void DFSmaster(string name_fout) {
        ofstream fout(name_fout);
        vector<bool> isVisited(MAX_VERTICES + 1, false);
        vector<int> v;
        for(int i = 1; i <= this->V; ++i)
            if(!isVisited[i])
                DFS(i, isVisited, v);
        vector<int>::reverse_iterator it;
        for(it = v.rbegin(); it != v.rend(); ++it)
            fout << *it << " ";
        fout << "\n";
        fout.close();
    }
};

int main() {
    Graph G;
    G.readGraph("sortaret.in");
    G.DFSmaster("sortaret.out");
    return 0;
}