Cod sursa(job #2294467)

Utilizator AntoniooMacovei Antonio Antonioo Data 2 decembrie 2018 14:28:54
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include<vector>
#include<stack>

using namespace std;

std::stack<int> topologicalSortUtil(const std::vector<std::vector<int> >& graph, int current,
                                    std::stack<int>& s, std::vector<bool>& visited) {

    // Mark the current node as visited
    visited[current] = true;

    // Recur for all the neighbors to current vertex
    for(int i = 0; i < graph[current].size(); i++) {
        if(!visited[graph[current][i]]) {
            topologicalSortUtil(graph, graph[current][i], s, visited);
        }
    }
    s.push(current);
    return s;
}

std::stack<int> topologicalSort(const std::vector<std::vector<int> >& graph) {
    stack<int> s;
    vector<bool> visited(graph.size(), false);
    for(int i = 0; i < graph.size(); i++) {
        if(!visited[i]) {
            topologicalSortUtil(graph, i, s, visited);
        }
    }
    return s;

}

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int n, m, src, dst;
    scanf("%d%d", &n, &m);

    std::vector<std::vector<int> > graph(n);

    for(int i = 0; i < m; i++) {
        scanf("%d%d", &src, &dst);
        graph[src - 1].push_back(dst - 1);
    }

    stack<int> s;
    s = topologicalSort(graph);

    while(!s.empty()) {
        printf("%d ", s.top() + 1);
        s.pop();
    }
    printf("\n");

    return 0;
}