Cod sursa(job #2193968)

Utilizator pakistanezuPopescu Alexandru Gabriel pakistanezu Data 11 aprilie 2018 20:57:27
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <bits/stdc++.h>

#define NMAX 100001
std::ifstream f("sortaret.in");
std::ofstream g("sortaret.out");

class Task {
public:
    void solve() {
        read_input();
        get_result();
    }
private:
    int n, m;
    std::vector<int> adj[NMAX];

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

    void get_result() {
        std::vector<bool> visited(n + 1, false);
        std::vector<int> result;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                dfs(i, visited, result);
            }
        }
        std::reverse(result.begin(), result.end());
        for (auto &node : result) {
            g << node << ' ';
        }
    }

    void dfs(int node, std::vector<bool> &visited, std::vector<int> &result) {
        visited[node] = true;
        for (auto &v : adj[node]) {
            if (!visited[v]) {
                dfs(v, visited, result);
            }
        }
        result.push_back(node);
    }
};
int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}