Cod sursa(job #2594767)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 6 aprilie 2020 16:47:36
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda laborator_7_sd_313cab Marime 0.9 kb
#include <fstream>
#include <vector>

#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], int rez[NMAX], int &nr) {
    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, rez, nr);
        }
    }
    rez[++nr] = node;
}

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

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

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

    for (int i = 1 ; i <= nr ; i++) {
        g<<rez[i]<<' ';
    }
    return 0;
}