Cod sursa(job #3206347)

Utilizator BoggiGurau Bogdan Boggi Data 22 februarie 2024 13:33:40
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

#define QI queue<int>
#define VI vector<int>
#define VB vector<bool>
#define VVI vector<VI>

int n, m;
VVI adList;
QI coada;
VB elim;
VI gradInt;

void sortT() {
    bool sortat;
    do {
        sortat = true;
        for (int i = 1; i <= n; ++i) {
            if (!elim[i] && gradInt[i] == 0) {
                elim[i] = true;
                coada.push(i);
                for (int j = 0; j < adList[i].size(); ++j) {
                    --gradInt[adList[i][j]];
                }
                sortat = false;
            }
        }
    } while(!sortat);
}

void printAd() {
    for (int i = 1; i <= n; ++i) {
        for(auto e: adList[i]) {
            fout << e << ' ';
        }
        fout << '\n';
    }
}

int main() {
    fin >> n >> m;
    adList = VVI(n + 1);
    elim = VB(n + 1, false);
    gradInt = VI(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        adList[x].push_back(y);
        ++gradInt[y];
    }
    sortT();

    while (!coada.empty()) {
        fout << coada.front() << ' ';
        coada.pop();
    }
}
//caut in adList[n] daca gasesc size == 0, caz in care          
// lucreaza cu gradul interior, si gradul exterior