Pagini recente » Cod sursa (job #871434) | Cod sursa (job #433295) | Cod sursa (job #2678494) | Cod sursa (job #1378457) | Cod sursa (job #1455505)
#include <stdio.h>
#include <list>
#include <vector>
using namespace std;
#define NEW 0
#define WORKING 1
#define READY 2
typedef struct {
int n;
vector <vector <int> > vertices;
} Graph, *aGraph;
aGraph readGraph (FILE *in) {
aGraph aG = new Graph;
int n, m;
fscanf(in, "%d %d", &n, &m);
for (int i = 0; i < n + 1; ++i) {
vector <int> v;
aG->vertices.push_back(v);
}
aG->n = n;
for (int i = 0; i < m; ++i) {
int x, y;
fscanf(in, "%d %d", &x, &y);
aG->vertices[x].push_back(y);
}
return aG;
}
void dfs (aGraph aG, list <int> *l, char *nodes, int id) {
if (nodes[id] == NEW) {
nodes[id] = WORKING;
for (unsigned int i = 0; i < aG->vertices[id].size(); ++i) {
dfs(aG, l, nodes, aG->vertices[id][i]);
}
nodes[id] = READY;
(*l).push_front(id);
}
}
int main (void) {
FILE *in = fopen("sortaret.in", "r");
aGraph aG = readGraph(in);
fclose(in);
list <int> l;
char *nodes = new char[aG->n + 1]();
for (int i = 1; i <= aG->n; ++i) {
dfs(aG, &l, nodes, i);
}
FILE *out = fopen("sortaret.out", "w");
while (l.size()) {
fprintf(out, "%d ", l.front());
l.pop_front();
}
fclose(out);
for (int i = 0; i < aG->n; ++i) {
aG->vertices[i].clear();
}
aG->vertices.clear();
l.clear();
delete aG;
delete[] nodes;
return 0;
}