Cod sursa(job #2224756)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 24 iulie 2018 23:06:25
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

void dfs(const vector<vector<int>>& graph, int node, vector<bool>& visited, vector<int>& topSort){
    visited[node] = true;

    for (int x: graph[node])
        if (!visited[x - 1])
            dfs(graph, x - 1, visited, topSort);

    topSort.push_back(node);
}

int main() {
    //ifstream cin("data.txt");
    ifstream cin("sortaret.in");
    ofstream cout("sortaret.out");

    ios_base::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N);

    while (M--){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
    }

    vector<bool> visited(N);
    vector<int> topSort;

    for (int i = 0; i < N; i++)
        if (!visited[i])
            dfs(graph, i, visited, topSort);

    reverse(topSort.begin(), topSort.end());

    for (int x: topSort)
        cout << x + 1 << " ";
    cout << endl;

    return 0;
}