Cod sursa(job #3265677)

Utilizator THEO0808Teodor Lepadatu THEO0808 Data 2 ianuarie 2025 13:46:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>

class Graf_orientat {
private:
    std::vector<std::vector<int>> L; // Adjacency list
    std::vector<int> vis;            // Visited array for DFS
    int num_nodes;                   // Number of nodes

public:
    explicit Graf_orientat(int num_nodes) : num_nodes(num_nodes) {
        L.resize(num_nodes + 1);
        vis.resize(num_nodes + 1, 0);
    }

    void add_edge(int u, int v) {
        L[u].push_back(v);
    }

    void dfs(int node, std::vector<int>& top_order) {
        vis[node] = 1;
        for (auto next : L[node]) {
            if (!vis[next]) {
                dfs(next, top_order);
            }
        }
        top_order.push_back(node);
    }

    std::vector<int> sortare_topologica() {
        std::vector<int> top_order;
        for (int i = 1; i <= num_nodes; ++i) {
            if (!vis[i]) {
                dfs(i, top_order);
            }
        }
        std::reverse(top_order.begin(), top_order.end());
        return top_order;
    }
};

int main() {
    std::ifstream infile("sortaret.in");
    std::ofstream outfile("sortaret.out");

    if (!infile.is_open() || !outfile.is_open()) {
        std::cerr << "Error opening input or output file." << std::endl;
        return 1;
    }

    int N, M;
    infile >> N >> M;

    Graf_orientat g(N);

    for (int i = 0; i < M; ++i) {
        int X, Y;
        infile >> X >> Y;
        g.add_edge(X, Y);
    }

    std::vector<int> topo_sort = g.sortare_topologica();

    for (size_t i = 0; i < topo_sort.size(); ++i) {
        if (i > 0) {
            outfile << " ";
        }
        outfile << topo_sort[i];
    }
    outfile << std::endl;

    infile.close();
    outfile.close();

    return 0;
}