Cod sursa(job #3123247)

Utilizator adaxndDobrica Nicoleta Adriana adaxnd Data 22 aprilie 2023 18:20:02
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 200000

using namespace std;

void dfs_recursive(int node, vector<int>adj[NMAX], vector<bool> &visited, vector<int> &sorted) {
    visited[node] = true;

    for (auto neigh : adj[node]) {
        if (!visited[neigh]) {
            dfs_recursive(neigh, adj, visited, sorted);
        }
    }

    sorted.push_back(node);
}

vector<int> dfs(int n, int m, vector<int>adj[NMAX]) {
    vector<bool> visited(n + 1, false);
    vector<int> sorted;

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs_recursive(i, adj, visited, sorted);
        }
    }

    return sorted;
}


int main() {
    int n, m;

    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    fin >> n >> m;

    vector<int> adj[n + 1];

    for (int i = 1, x, y; i <= m; ++i) {
        fin >> x >> y;
        adj[x].push_back(y);
    }

    vector<int> sorted = dfs(n, m, adj);
    
    for (int i = n - 1; i >= 0; --i) {
        fout << sorted[i] << ' ';
    }

    return 0;
}