Cod sursa(job #1480489)

Utilizator stoianmihailStoian Mihail stoianmihail Data 2 septembrie 2015 17:46:54
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#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;
}