Cod sursa(job #2963285)

Utilizator rastervcrastervc rastervc Data 10 ianuarie 2023 18:44:56
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

constexpr size_t LIM = 5 * 1e4 + 1;
int N, M, node1, node2, indegree[LIM];
vector<int> adj_list[LIM];
bool visited[LIM];

// Algoritmul lui Kahn
static inline vector<int> topological_ordering() {
    vector<int> ans;

    queue<int> q;
    for (int i = 1; i <= N; ++i)
        if (!indegree[i]) q.push(i);

    while (!q.empty()) {
        const int node = q.front();
        q.pop();
        ans.push_back(node);
        for (const int adj : adj_list[node]) {
            --indegree[adj];
            if (indegree[adj] == 0)
                q.push(adj);
        }
    }

    return ans;
}

int main() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> node1 >> node2;
        adj_list[node1].push_back(node2);
        ++indegree[node2];
    }

    vector<int> ans = topological_ordering();

    for (const int node : ans)
        fout << node << ' ';

    fin.close();
    fout.close();
    return 0;
}