Cod sursa(job #3295809)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 8 mai 2025 17:07:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;


int main() {

    ifstream infile;
    infile.open("sortaret.in");

    int n, m, x, y;
    infile >> n >> m;

    vector<vector<int>> arcs(n + 1);
    vector<int> revarcs(n + 1, 0);
    vector<int> res;

    for(int i = 1; i<= m; ++i) {
        infile >> x >> y;
        arcs[x].push_back(y);
        ++revarcs[y];
    }

    infile.close();

    queue<int> q;

    for(int i=1; i<=n; ++i) {
        if (revarcs[i] == 0) {
            q.push(i);
        }
    }

    while (! q.empty()) {
        x = q.front();
        q.pop();
        res.push_back(x);

        for(int i = 0; i<arcs[x].size(); ++i) {
            y = arcs[x][i];
            --revarcs[y];
            if(revarcs[y] == 0) {
                q.push(y);
            }
        }
    }
    

    ofstream outfile;
    outfile.open("sortaret.out");

    for(int i=0; i < res.size(); ++i)
        outfile << res[i] << ' ';
    outfile << '\n';
    
    outfile.close();
    return 0;
}