Cod sursa(job #3225378)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 17 aprilie 2024 14:43:02
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Solutuion {
 private:
    size_t N;
    size_t M;
    size_t source;
    vector<vector<size_t>> adj;
    vector<int> in_rank;

 public:
    explicit Solutuion(ifstream &in) {
        in >> N >> M;
        adj.resize(N + 1);
        in_rank.resize(N + 1, 0);

        size_t node1, node2;
        for (size_t i = 1; i <= M; i++) {
            in >> node1 >> node2;

            adj[node1].push_back(node2);
            ++in_rank[node2];
        }
    }

    vector<int> solve() {
        vector<int> topsort;
        topsort.reserve(N);

        vector<bool> sorted(N + 1, false);

        queue<int> q;

        for (int source = 1; source < N + 1; source++)
            if (in_rank[source] == 0)
                q.push(source);

        while (!q.empty()) {
            int curr_node = q.front();
            q.pop();

            topsort.push_back(curr_node);

            for (auto neigh : adj[curr_node]) {
                if (--in_rank[neigh] == 0) {
                    q.push(neigh);
                }
            }
        }

        return topsort;
    }
};

int main() {
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    
    vector<int> solution = Solutuion(in).solve();
    copy(solution.begin(), solution.end(), ostream_iterator<int>(out, " "));
    
    in.close();
    out.close();
    return 0;
}