Cod sursa(job #2595087)

Utilizator arinaturcuArina Turcu arinaturcu Data 7 aprilie 2020 01:05:52
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <list>
#include <vector>

#define MAX_NODES 50010
  
using namespace std;

void addEdge(vector<int> lg[], int u, int v) { 
    lg[u].push_back(v);
} 

void dfs(vector<int> lg[], int node, int N, int *visited, stack<int> *st) {
    visited[node] = 1;

    for (int i = 1; i <= N; ++i) {
        if (visited[i] == 0) {
            dfs(lg, i, N, visited, st);
        }
    }

    (*st).push(node);
}
  
// void topo_sort(vector<int> lg[], int N) {

// }

int main() { 
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    int N, M, time = 0;
    int sur, des;
    stack<int> st;

    in >> N >> M;

    vector<int> lg[N+1];
    int visited[N+1] = {0}, t_desc[N+1], t_fin[N+1];

    for (int i = 0; i < M; ++i) {
        in >> sur >> des;
        addEdge(lg, sur, des);
    }

    dfs(lg, 1, N, visited, &st);

    while (!st.empty()) { 
        out << st.top() << ' '; 
        st.pop(); 
    }
 
    in.close();
    out.close();
  
    return 0; 
}