Pagini recente » Cod sursa (job #2544005) | Cod sursa (job #1856792) | Cod sursa (job #2028335) | Cod sursa (job #2524271) | Cod sursa (job #1480489)
#include <stdio.h>
#define Smerenie 100001
#define Nadejde 50001
typedef struct {
int v, next;
} list;
int N, M;
int adj[Nadejde]; // capetele listelor de adiacenta.
list l[Smerenie]; // lista arcelor alocata static.
char seen[Nadejde]; // seen[u] este 1 doar daca l-am vazut pe "u" in dfs().
int numSeen, order[Nadejde]; // sortarea topologica a grafului.
/** Adauga-l pe "v" la lista de adiacenta a lui "u". **/
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
/** Exploreaza recursiv nodul "u". **/
void dfs(int u) {
int pos;
if (!seen[u]) {
seen[u] = 1;
for (pos = adj[u]; pos; pos = l[pos].next) {
dfs(l[pos].v);
}
order[++numSeen] = u;
}
}
/** Sortarea topologica a grafului. **/
void topSort() {
int u;
for (u = 1; u <= N; u++) {
dfs(u);
}
}
int main(void) {
int i, u, v;
FILE *f = fopen("sortaret.in", "r");
/* Citim graful. */
fscanf(f, "%d %d", &N, &M);
for (i = 1; i <= M; i++) {
fscanf(f, "%d %d", &u, &v);
addEdge(u, v, i);
}
fclose(f);
f = fopen("sortaret.out", "w");
topSort();
while (numSeen) {
fprintf(f, "%d ", order[numSeen--]);
}
fputc('\n', f);
fclose(f);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}