Pagini recente » Cod sursa (job #746102) | Cod sursa (job #2462139) | Cod sursa (job #2273978) | Cod sursa (job #2522042) | Cod sursa (job #2772851)
#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;
}