Pagini recente » Cod sursa (job #36098) | Cod sursa (job #2026190) | Cod sursa (job #1439931) | Cod sursa (job #2968202) | Cod sursa (job #1341718)
#include <stdio.h>
#include <string.h>
#define INCR 100
#define WHITE 0
#define GREY 1
#define BLACK 2
struct node {
int n;
int crt;
int max;
node **next;
void init (int i);
};
void node::init (int i) {
n = i;
crt = 0;
max = INCR;
next = new node *[INCR];
}
void increase (node *N) {
N->max += INCR;
node **temp = new node *[N->max];
memcpy(temp, N->next, N->crt * sizeof(node *));
N->next = temp;
}
void add (node *N, int i, int j) {
if (N->crt == N->max) {
increase(N);
}
N[j].next[N[j].crt] = &N[i];
++(N[j].crt);
}
int read(FILE *in, node **N) {
int n, m;
fscanf(in, "%d %d", &n, &m);
node *temp = new node[n];
for (int i = 0; i < n; i++) {
temp[i].init(i+1);
}
// add(temp, n-1, m-1);
for (int i = 0; i < m; i++) {
int x, y;
fscanf(in, "%d %d", &x, &y);
add(temp, x-1, y-1);
}
*N = temp;
return n;
}
void intest (node *N, int n) {
for (int i = 0; i < n; i++) {
printf("%d: ", N[i].n);
for (int j = 0; j < N[i].crt; j++) {
printf("%d ", N[i].next[j]->n);
}
printf("\n");
}
}
void visit(node *n, short *color, node **sorted, int *crt) {
color[n->n-1] = GREY;
for (int i = 0; i < n->crt; i++) {
if (color[n->next[i]->n-1] == WHITE) {
visit(n->next[i], color, sorted, crt);
}
}
color[n->n-1] = BLACK;
sorted[*crt] = n;
(*crt)++;
}
void tsort (node *N, node **sorted, int n) {
int crt = 0;
short color[n+1];
memset(color, 0, (n+1) * sizeof(short));
for (int i = 0; i < n; i++) {
if (color[i] == WHITE) {
visit(&N[i], color, sorted, &crt);
}
}
}
int main (void) {
FILE *in = fopen("sortaret.in", "r");
FILE *out = fopen("sortaret.out", "w");
node *N;
int n = read(in, &N);
//intest(N, n);
node **sorted = new node *[n];
tsort(N, sorted, n);
for (int i = 0; i < n; i++) {
fprintf(out, "%d ", sorted[i]->n);
}
printf("\n");
return 0;
}