Pagini recente » Cod sursa (job #2784207) | Cod sursa (job #1204569) | Cod sursa (job #2365229) | Cod sursa (job #248133) | Cod sursa (job #462986)
Cod sursa(job #462986)
// 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
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 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] ++;
}
int *Queue = (int*)calloc(n, sizeof(int)), u;
a = b = 0;
for (i = 0; i < n; ++ i)
if (Deg[i] == 0) {
Queue[b ++] = i;
Used[i] = 1;
}
while (a < b) {
u = Queue[a ++];
for (i = 0; i < numNext[u]; ++ i) {
if (Used[Next[u][i]] == 1) {
printf("Exista ciclu: (%d %d)\n", u, Next[u][i]);
goto end;
}
Deg[Next[u][i]] --;
if (Deg[Next[u][i]] == 0) {
Queue[b ++] = Next[u][i];
Used[Next[u][i]] = 1;
}
}
printf("%d ", u + 1);
}
end:
free(Queue);
for (i = 0; i < n; ++ i)
free(Next[i]);
free(Next);
free(numNext);
free(Used);
free(Deg);
return 0;
}