Cod sursa(job #2594801)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 6 aprilie 2020 17:14:24
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 0.89 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMAX 50001

using namespace std;

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

void DFS(int node, vector <int> edge_list[NMAX], bool visited[NMAX], stack <int> &st) {
    visited[node] = 1;
    for (int i = 0 ; i < edge_list[node].size() ; i++) {
        if (visited[edge_list[node][i]] == 0) {
            DFS(edge_list[node][i], edge_list, visited, st);
        }
    }
    st.push(node);
}

int main()
{
    int N, M, x, y;
    vector <int> edge_list[NMAX];

    f>>N>>M;
    for(int i = 0 ; i < M ; i++) {
        f>>x>>y;
        edge_list[x].push_back(y);
    }

    bool visited[NMAX];
    stack <int> st;
    for (int i = 1 ; i <= N ; i++) {
        if (visited[i] == 0) {
            DFS(i, edge_list, visited, st);
        }
    }

    while (st.empty() == 0) {
        g<<st.top()<<' ';
        st.pop();
    }
    return 0;
}