Cod sursa(job #3330281)

Utilizator AlexN_04Nedelcu Alex AlexN_04 Data 18 decembrie 2025 14:29:22
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<int> sortareTopologica(vector<vector<int>> &la, vector<int> &gradInt, int N) {
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (gradInt[i] == 0) {
            q.push(i);
        }
    }
    vector<int> sortTop;
    while (!q.empty()) {
        int crt = q.front();
        q.pop();

        sortTop.push_back(crt);

        for (int& vecin : la[crt]) {
            gradInt[vecin]--;
            if (gradInt[vecin] == 0) {
                q.push(vecin);
            }
        }
    
    }

    return sortTop;
}

int main() {
    int N, M;
    fin >> N >> M;

    vector<vector<int>> la(N + 1);
    vector<int> gradInt(N + 1, 0);
    for (int i = 0; i < M; i++) {
        int x, y;
        fin >> x >> y;

        gradInt[y]++;
        la[x].push_back(y);
    }
    
    vector<int> sortTop = sortareTopologica(la, gradInt, N);

    for (int& x : sortTop) {
        fout << x << ' ';
    }
}