Cod sursa(job #2595340)

Utilizator preda.andreiPreda Andrei preda.andrei Data 7 aprilie 2020 16:05:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int kNmax = 100005;

class Task {
    public:
        void solve() {
            read_input();
            print_output(get_result());
        }

    private:
        int n;
        int m;
        vector<int> adj[kNmax];

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

        vector<int> find_degrees() {
            vector<int> degrees(n + 1, 0);
            for (int i = 1; i <= n; i += 1) {
                for (const auto &next : adj[i]) {
                    degrees[next] += 1;
                }
            }
            return degrees;
        }

        queue<int> init_queue(const vector<int> &degrees) {
            queue<int> q;
            for (int i = 1; i <= n; i += 1) {
                if (degrees[i] == 0) {
                    q.push(i);
                }
            }
            return q;
        }

        vector<int> get_result() {
            auto degrees = find_degrees();
            auto q = init_queue(degrees);

            vector<int> topsort;
            while (!q.empty()) {
                auto node = q.front();
                q.pop();

                topsort.push_back(node);
                for (const auto &next : adj[node]) {
                    degrees[next] -= 1;
                    if (degrees[next] == 0) {
                        q.push(next);
                    }
                }
            }
            return topsort;
        }

        void print_output(vector<int> result) {
            ofstream fout("sortaret.out");
            for (int i = 0; i < int(result.size()); i++) {
                fout << result[i] << ' ';
            }
            fout << "\n";
        }
};

int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}