Cod sursa(job #3029947)

Utilizator CalinHanguCalinHangu CalinHangu Data 17 martie 2023 12:06:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

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

const int NMAX = 50005;
const int INF = 1e9 + 7;
const char nl = '\n';

int n, m, f[NMAX];

vector<int> v[NMAX], order;

void dfs(int node){
    f[node] = 1;
    for(auto i: v[node]){
        if(!f[i])
            dfs(i);
    }
    order.pb(node);
}

void toposort(){
    for(int i = 1; i <= n; ++i){
        if(!f[i])
            dfs(i);
    }
    reverse(order.begin(), order.end());
    for(auto i: order)
        out << i << ' ';
    out << nl;
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; ++i){
        int a, b;
        in >> a >> b;
        v[a].pb(b);
    }
    toposort();
    return 0;
}