Pagini recente » Cod sursa (job #1095037) | Cod sursa (job #2565315) | Cod sursa (job #2190651) | Cod sursa (job #702500) | Cod sursa (job #463002)
Cod sursa(job #463002)
// http://infoarena.ro/problema/sortaret
#include <stdio.h>
#include <stdlib.h>
#include <assert.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 i;
for (i = 0; i < numNext[a]; ++ i)
if (!Used[Next[a][i]]) {
Used[Next[a][i]] = 1;
depthFirst(Next[a][i]);
}
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));
for (i = 0; i < n; ++ i)
if (Deg[i] == 0) {
Used[i] = 1;
depthFirst(i);
}
assert(numStack == n);
for (i = numStack - 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;
}