Cod sursa(job #2801511)

Utilizator Cezar211Popoveniuc Cezar Cezar211 Data 16 noiembrie 2021 14:07:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

#define NMAX 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

inline void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

vector<int> v[NMAX];
bitset<NMAX> viz;
int N, M;
void dfs(int nod, vector<int>& res) {
    viz[nod] = true;
    for (auto it: v[nod])
        if (!viz[it])
            dfs(it, res);
    res.push_back(nod);
}

vector<int> topologicalSort() {
    vector<int> res;
    for(int i=1; i<=N; i++)
        if(!viz[i]) {
            dfs(i, res);
        }
    std::reverse(res.begin(), res.end());
    return res;
}

int main() {
    fin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        v[x].push_back(y);
    }
    vector<int> res = topologicalSort();
    for (auto it: res)
        fout << it << ' ';
    return 0;
}