Cod sursa(job #3206294)

Utilizator BoggiGurau Bogdan Boggi Data 22 februarie 2024 11:09:39
Problema Sortare topologica Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

#define SI stack<int>
#define VI vector<int>
#define VB vector<bool>
#define VVI vector<VI>

int n, m;
VVI adList;
SI stiva;
VB elim;

void elimNode(int node) {
    for (int i = 1; i <= n; ++i) {
        for(int j = 0; j < adList[i].size(); ++j) {
            if (adList[i][j] == node) {
                adList[i].erase(adList[i].begin() + j);
                j = adList[i].size();
            }
        }
    }
}

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);
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        adList[x].push_back(y);
    }
    //printAd();
    bool elimAll;
    do {
        elimAll = true;
        for (int i = n; i >= 1; --i) {
            if (adList[i].empty() && !elim[i]) {
                //fout << i << '\n';
                stiva.push(i);
                elimAll = false;
            }
        }
        SI copy = stiva;
        while (!copy.empty()) {
            if (!elim[copy.top()]) {
                elim[copy.top()] = true;
                elimNode(copy.top());
            }
            copy.pop();
        }
    } while(!elimAll);
    while (!stiva.empty()) {
        fout << stiva.top() << ' ';
        stiva.pop();
    }
}

//caut in adList[n] daca gasesc size == 0, caz in care