Cod sursa(job #2285450)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 18 noiembrie 2018 16:41:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector<vector<int> > graph;
vector<bool> seen;
stack<int> topological_sorting;

void read() {
    int source, target;

    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        graph.push_back(vector<int>());
        seen.push_back(false);
    }

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

void dfs(int node) {
    seen[node] = true;

    for (vector<int>::iterator it = graph[node].begin(); it != graph[node].end(); it++) {
        if (!seen[*it]) {
            dfs(*it);
        }
    }

    topological_sorting.push(node);
}

int main() {
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    read();

    for (int i = 0; i < n; i++) {
        if (!seen[i]) {
            dfs(i);
        }
    }
    while (!topological_sorting.empty()) {
        printf("%d ", topological_sorting.top() + 1);
        topological_sorting.pop();
    }
}