Cod sursa(job #3317462)

Utilizator StefanL2005Stefan Leustean StefanL2005 Data 23 octombrie 2025 17:46:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in ("sortaret.in");
ofstream out ("sortaret.out");

void DFS_TOP(int node, vector<vector<int>> &graf, vector<bool> &visited, vector<int> &top) {
    visited[node] = true;
    for (auto v : graf[node])
        if (visited[v] == false) {
            DFS_TOP(v, graf, visited, top);
        }
    top.push_back(node);
}


int main() {
    int n, m;
    in >> n >> m;

    vector<vector<int>> graf(n);

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        x--; y--;

        graf[x].push_back(y);
    }

    vector<bool> visited(n, false);
    vector<int> top;

    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            DFS_TOP(i, graf, visited, top);

    for (int i = n - 1; i >= 0; i--)
        out << top[i] + 1 << " ";

    return 0;
}