Cod sursa(job #3230044)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 18 mai 2024 21:47:52
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <queue>
#include <vector>

#define NMAX 50000


#define NOTVISITED 0
#define VISITED 1


void dfs(int source, std::vector<int> adj[], int vis[], std::vector<int> &st)
{
    vis[source] = VISITED;

    for (auto neigh : adj[source])
        if (!vis[neigh])
            dfs(neigh, adj, vis, st);

    st.push_back(source);
}

int main()
{
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");

    int n, m, source;
    std::vector<int> adj[NMAX], st;
    int vis[NMAX] = {NOTVISITED};


    fin >> n >> m;

    for (int v, w, i = 0; i < m; ++i) {
        fin >> v >> w;
        adj[v - 1].push_back(w - 1);
    }


    dfs(0, adj, vis, st);


    for (auto node = st.rbegin(); node != st.rend(); ++node)
        fout << *node + 1 << ' ';

    fout << '\n';


    fin.close();
    fout.close();

    return 0;
}