Pagini recente » Cod sursa (job #1609848) | Cod sursa (job #1242255) | Cod sursa (job #792445) | Cod sursa (job #1291170) | Cod sursa (job #1592933)
#include <stdio.h> /* sortarea topologica: un graf orientat fara cicluri se poate sorta topologic -
#include <stdlib.h> numarul de ordine al fiecarui nod trebuie sa fie mai mare decat numerele de
ordine ale parintilor(daca muchia (u,v) apartine grafului u trebuie sa apara
in sortare inaintea lui v */
#define NMAX 5005
int n, m, t;
int x[NMAX][NMAX];
int viz1[NMAX], viz2[NMAX];
struct node {
int inf;
struct node *pnext;
};
struct node *h; /* *h este variabila globala */
void push(int x) {
struct node *p;
p = (struct node*) malloc(sizeof(struct node));
p->inf = x;
p->pnext = h;
h = p;
}
void df(int u) {
int v;
if (viz1[u] == 0) {
viz1[u] = t;
t++;
for (v = 1; v <= n; v++)
if (x[u][v] == 1) df(v);
viz2[u] = t;
push(u);
t++;
}
}
int main() {
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
int i, j, k;
struct node *pc;
scanf("%d", &n);
scanf("%d", &m);
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
x[i][j] = 0;
}
}
for (k = m; k >= 1; k--) {
scanf("%d%d", &i, &j);
x[i][j] = 1;
}
h = NULL;
for (i = 0; i <= n; i++) {
viz1[i] = 0;
viz2[i] = 0;
}
t = 1;
for (i = 1; i <= n; i++) {
if (viz1[i] == 0) {
df(i);
}
}
pc = h;
while (pc != NULL) {
printf("%d ", pc->inf);
pc = pc->pnext;
}
printf("\n");
return 0;
}