Cod sursa(job #3322138)

Utilizator costelus18Catalin Dohotaru costelus18 Data 12 noiembrie 2025 21:22:34
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > adj_list;
vector<int> in_degree;
int N;

void read_input() {
    ifstream input("sortaret.in");
    int M;
    input >> N >> M;
    adj_list.resize(N + 1);
    in_degree.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v;
        input >> u >> v;
        if (find(adj_list[u].begin(), adj_list[u].end(), v) != adj_list[u].end())
            continue; // ignore duplicate edges
        adj_list[u].push_back(v);
    }
}

vector<int> topo_sort() {
    vector<int> topo_list;
    queue <int> free_nodes;
    for (int i = 1; i <= N; i++)
        if (in_degree[i] == 0)
            free_nodes.push(i);
    while (!free_nodes.empty()) {
        int u = free_nodes.front();  free_nodes.pop();
        topo_list.push_back(u);
        for (int neigh : adj_list[u]) {
            in_degree[neigh]--;
            if (in_degree[neigh] == 0)
                free_nodes.push(neigh);
        }
    }
    return topo_list;
}

int main() {
    read_input();
    vector<int> topo_list = topo_sort();
    ofstream output("sortaret.out");
    for (int u: topo_list)
        output << u << " ";
    return 0;
}