Cod sursa(job #3292937)

Utilizator daristyleBejan Darius-Ramon daristyle Data 9 aprilie 2025 19:48:58
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NODES_MAX = 5e4;
vector<int> edge[NODES_MAX];
vector<int> order;
bool marked[NODES_MAX];

inline void addEdge(int u, int v){
    edge[v].push_back(u);
}

void dfs(const int& node, const vector<int> *edge, vector<int>& visited){
    marked[node] = true;

    for(auto neighbour: edge[node])
        if(!marked[neighbour])
            dfs(neighbour, edge, visited);

    visited.push_back(node);
}

int main(){
    int nodes, edges, u, v;
    fin >> nodes >> edges;
    for(int i = 0; i < edges; ++i){
        fin >> u >> v;

        addEdge(u - 1, v - 1);
    }

    for(int node = 0; node < nodes; ++node)
        if(!marked[node])
            dfs(node, edge, order);

    for(auto x: order){
        fout << x + 1 << ' ';
    }
    fout << '\n';

    fin.close();
    fout.close();
    return 0;
}