Cod sursa(job #2595082)

Utilizator arinaturcuArina Turcu arinaturcu Data 7 aprilie 2020 00:45:28
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <queue>
#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, int *t_desc, int *t_fin, int *time, int *max, int *sorted, int *k) {
    visited[node] = 1;
    t_desc[node] = *time;
    (*time)++;

    for (int i = 1; i <= N; ++i) {
        if (visited[i] == 0) {
            dfs(lg, i, N, visited, t_desc, t_fin, time, max, sorted, k);
        }
    }

    t_fin[node] = *time;
    (*time)++;
    sorted[(*k)++] = node;
}
  
int main() { 
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    int N, M, time = 0, max = 0, k = 1;
    int sur, des;

    in >> N >> M;

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

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

    dfs(lg, 1, N, visited, t_desc, t_fin, &time, &max, sorted, &k);

    for (int i = N; i > 0; --i) {
        out << sorted[i] << ' ';
    }
 
    in.close();
    out.close();
  
    return 0; 
}