Cod sursa(job #2772851)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 3 septembrie 2021 00:58:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.14 kb
#include <fstream>
#include <list>
#include <utility>

using namespace std;

#define value(u) u.first
#define hasAllChildrenBlack(u) u.second

#define asRoot true
#define asChild false

enum color {
    WHITE, GRAY, BLACK
};

void explore(int x, list<int> *adj, enum color *col, list<int> &ordering);

void topSort(list<int> *adj, int n, list<int> &ordering) {
    enum color col[n];
    int u;

    for (u = 0; u < n; u++)
        col[u] = WHITE;

    for (u = 0; u < n; u++)
        if (col[u] == WHITE)
            explore(u, (list<int> *) adj, col, ordering);
}

// exploreaza fiecare componenta conexa din graf
void explore(int x, list<int> *adj, enum color *col, list<int> &ordering) {
    list<pair<int, bool>> s;
    // x e vazut ca un copil din perspectiva forului din topSort care ia toate 
    // nodurile la rand
    s.push_back({x, asChild});

    while (!s.empty()) {
        auto u = s.back();
        s.pop_back();

        if (hasAllChildrenBlack(u)) {
            // col[node(u)] = BLACK;
            ordering.push_front(value(u));
            continue;
        }

        if (col[value(u)] != WHITE)
            continue;
        col[value(u)] = GRAY;

        // il pun pe u pe stiva ca radacina a tuturor copiilor sai (chiar daca
        // unii deja au fost explorati)
        // ma intereseaza ca atunci cand toti fiii sai vor fi terminati de
        // explorat si il scot pe u de pe stiva, aceasta valoare asRoot sa imi
        // spuna ca il pot adauga pe u in lista cu nodurile sortate
        s.push_back({value(u), asRoot});

        for (int v : adj[value(u)])
            if (col[v] == WHITE)
                s.push_back({v, asChild});
    }
}

int main(void) {
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    int n, m;
    in >> n >> m;

    list<int> adj[n];

    int i, x, y;

    for (i = 0; i < m; i++) {
        in >> x >> y;
        adj[--x].push_back(--y);
    }

    list<int> ordering;
    topSort((list<int> *) adj, n, ordering);

    while (!ordering.empty()) {
        int u = ordering.front();
        ordering.pop_front();
        out << ++u << ' ';
    }
    out << '\n';

    in.close();
    out.close();
    return 0;
}