Cod sursa(job #2772736)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 2 septembrie 2021 17:04:41
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <fstream>
#include <list>

using namespace std;

enum color {
    WHITE, GRAY, BLACK
};

void explore(int source, list<int> *adj, enum color *col, int *p,
            int *grayChildren, int n, list<int> &ordering);

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

    for (u = 0; u < n; u++) {
        grayChildren[u] = 0;
        p[u] = -1;
        col[u] = WHITE;
    }

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

void explore(int source, list<int> *adj, enum color *col, int *p,
            int *grayChildren, int n, list<int> &ordering) {
    list<int> s;
    s.push_back(source);

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

        col[u] = GRAY;

        for (int v : adj[u]) {
            if (col[v] == WHITE) {
                p[v] = u;
                s.push_back(v);
                grayChildren[u]++;
            }
        }

        // vad daca u are toti copiii negri sau nu are deloc copii, cazuri in
        // care nodul devine negru si il pun in lista ordonata pe care vreau sa
        // o construiesc
        if (grayChildren[u] == 0) {
            ordering.push_front(u);

            while (p[u] != -1) {
                grayChildren[p[u]]--;

                if (grayChildren[p[u]] == 0) {
                    // daca u e ultimul nod care ramasese de explorat dintre
                    // fiii parintelui sau, inseamna ca p[u] e urmatorul nod
                    // care devine negru dupa ce termin cu u
                    ordering.push_front(p[u]);
                } else {
                    // altfel mai sunt pe stiva copiii lui p[u] care au ramas
                    // de explorat
                    break;
                }
                u = p[u];
            }
        }
    }
}

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 < n; 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;
}