Cod sursa(job #2193975)

Utilizator pakistanezuPopescu Alexandru Gabriel pakistanezu Data 11 aprilie 2018 21:19:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 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];
    std::vector<int> in_degree;

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

    void get_result() {
        std::vector<int> result = bfs();
        for (auto &node : result) {
            g << node << ' ';
        }
    }

    std::vector<int> bfs() {
        std::queue<int> Q;
        std::vector<int> result;
        for (int i = 1;i <= n; ++i) {
            if (in_degree[i] == 0) {
                Q.push(i);
            }
        }
        while (!Q.empty()) {
            int node = Q.front();
            Q.pop();
            result.push_back(node);
            for (auto &v : adj[node]) {
                --in_degree[v];
                if (in_degree[v] == 0) {
                    Q.push(v);
                }
            }
        }
        bool found = true;
        for (int i = 1; i <= n; ++i) {
            if (in_degree[i] != 0) {
                found = false;
                break;
            }
        }
        if (found) {
            return result;
        }
        return {};
    }
};
int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}