Pagini recente » Cod sursa (job #2976520) | Cod sursa (job #1525736) | Cod sursa (job #2240727) | Cod sursa (job #2396993) | Cod sursa (job #462997)
Cod sursa(job #462997)
// http://infoarena.ro/problema/sortaret
#include <stdio.h>
#include <stdlib.h>
int **Next, // vecinii fiecarui nod
*numNext, // numarul de vecini ai fiecarui nod
n, m; // numarul de noduri respectiv muchii
int *Deg, // gradul fiecarui nod
*Stack; // pun pe stiva (privita ca vector), deci stiva e invers in memorie nodurile cand le termin de parcus; e echivalent cu o sortare dupa timpii de final
char *Used; // a fost vizitat sau nu
inline void addEdge(int a, int b) {
Next[a] = (int*)realloc(Next[a], (numNext[a] + 1) * sizeof(int));
Next[a][numNext[a] ++] = b;
}
int numStack = 0;
void depthFirst(int a, int color) {
Used[a] = color;
int i;
for (i = 0; i < numNext[a]; ++ i) {
if (!Used[Next[a][i]])
depthFirst(Next[a][i], color);
}
Stack[numStack ++] = a;
}
int main() {
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
scanf("%d%d", &n, &m);
Next = (int**)calloc(n, sizeof(int*));
numNext = (int*)calloc(n, sizeof(int));
Deg = (int*)calloc(n, sizeof(int));
Used = (char*)calloc(n, sizeof(char));
int i, a, b;
for (i = 0; i < m; ++ i) {
scanf("%d%d", &a, &b);
addEdge(a - 1, b - 1);
Deg[b - 1] ++;
}
Stack = (int*)calloc(n, sizeof(int));
int color = 1;
for (i = 0; i < m; ++ i)
if (Deg[i] == 0)
depthFirst(i, color ++);
for (i = n - 1; i >= 0; -- i)
printf("%d ", Stack[i] + 1);
for (i = 0; i < n; ++ i)
free(Next[i]);
free(Stack);
free(Next);
free(numNext);
free(Used);
free(Deg);
return 0;
}