Cod sursa(job #3230045)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 18 mai 2024 21:49:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 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;
    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);
    }

    for (int i = 0; i < n; ++i)
        if (!vis[i])
            dfs(i, adj, vis, st);


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

    fout << '\n';


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

    return 0;
}