Cod sursa(job #3258903)

Utilizator ShAwDoRneYNacu Gabriel ShAwDoRneY Data 24 noiembrie 2024 12:04:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <unordered_set>

using namespace std;

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

void DFS(int currentNode, vector<bool> &isVisited, vector<int> &path, vector<unordered_set<int>> &graph) {
    isVisited[currentNode] = true;

    for(auto neighbor : graph[currentNode]) {
        if(!isVisited[neighbor]) {
            DFS(neighbor, isVisited, path, graph);
        }
    }
    path.push_back(currentNode);
}

int main() {

    int noNodes, noEdges;
    vector<unordered_set<int>> graph;
    fin >> noNodes >> noEdges;
    graph.resize(noNodes+1);

    while(noEdges--) {
        int firstNode, secondNode;
        fin >> firstNode >> secondNode;
        graph[firstNode].insert(secondNode);
    }
    vector<bool> isVisited(noNodes+1, 0);
    vector<int> path;

    for(int i=1; i<=noNodes; i++) {
        if(!isVisited[i]) {
            DFS(i, isVisited, path, graph);
        }
    }

    for(int i = noNodes-1; i>=0; i--)
        fout << path[i] << ' ';

    return 0;
}