Cod sursa(job #2666924)

Utilizator dariahazaparuHazaparu Daria dariahazaparu Data 2 noiembrie 2020 16:43:48
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>

const int  N_MAX = 100005;

std :: vector<int> graph[N_MAX];
std :: vector<int> sorted;
bool vis[N_MAX];
int n, m;

void dfs(int node) {
    vis[node] = true;
    for (int i : graph[node]) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    sorted.push_back(node);
}

int main() {

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

    fin >> n >> m;
    for (int i = 1; i <= m ; ++i) {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
    }

    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i);
        }
    }

    std::reverse(sorted.begin(), sorted.end());
    for (int i : sorted)
        fout << i << " ";

    return 0;
}