Cod sursa(job #3122161)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 17 aprilie 2023 17:42:27
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
#define MAXN 50000

using namespace std;
using graph = vector<vector<int>>;

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

graph adj;
bitset<MAXN> visited;
stack<int> st;

void read() {
    int n, m;
    fin >> n >> m;
    adj = graph(n, vector<int>());
    for (int i = 0; i < m; i++) {
        int iNode, jNode;
        fin >> iNode >> jNode;
        iNode--, jNode--;
        adj[iNode].push_back(jNode);
    }
}

void dfs(int node) {
    visited[node] = true;
    for (auto& neighbour: adj[node])
        if (!visited[neighbour])
            dfs(neighbour);
    st.push(node);
}

void solve() {
    for (int node = 0; node < adj.size(); node++)
        if (!visited[node])
            dfs(node);
    while (!st.empty()) {
        fout << st.top() + 1 << ' ';
        st.pop();
    }
}

int main() {
    read();
    solve();
    return 0;
}