Cod sursa(job #3341605)

Utilizator ShokapKaplonyi Akos Shokap Data 20 februarie 2026 12:35:09
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>
#include <stack>

std::ifstream input ("sortaret.in");
std::ofstream output ("sortaret.out");

void dfs(std::vector<std::vector<int>>& graph, std::vector<int>& wasNodeVisited, std::stack<int>& outputStack, int startNode){
    std::stack<int> nodeStack;
    nodeStack.push(startNode);
    wasNodeVisited[startNode] = true;

    while(!nodeStack.empty()){
        int currentNode = nodeStack.top();

        bool validConnectionExistence = false;
        for(auto node : graph[currentNode]){
            if(!wasNodeVisited[node]){
                nodeStack.push(node);
                wasNodeVisited[node] = true;
                validConnectionExistence = true;
            }
        }
        if(!validConnectionExistence){
            nodeStack.pop();
            outputStack.push(currentNode);
        }
    }
}

int main () {

    int n, m;
    input >> n >> m;

    std::vector<std::vector<int>> graph(n+1);
    for(int i = 1; i <= m; i++){
        int a, b;
        input >> a >> b;
        //a connects to b
        graph[a].push_back(b);
    }

    std::vector<int> wasNodeVisited(n+1, false);
    wasNodeVisited[0] = true;
    std::stack<int> outputStack;

    for(int i = 1; i <= n; i++){
        if(!wasNodeVisited[i]){
            dfs(graph, wasNodeVisited, outputStack, i);
        }
    }
    while(!outputStack.empty()){
        output << outputStack.top() << ' ';
        outputStack.pop();
    }

    return 0;
}