Pagini recente » Cod sursa (job #1360810) | Cod sursa (job #1674723) | Cod sursa (job #517308) | Cod sursa (job #2136796) | Cod sursa (job #2772736)
#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;
}