Cod sursa(job #1706921)

Utilizator stoianmihailStoian Mihail stoianmihail Data 23 mai 2016 20:26:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>

#define Smerenie 100000
#define Nadejde 50000

#define u16 unsigned short

typedef struct {
  u16 int v;
  int next;
} list;

int N, M, ss;
int adj[Nadejde + 1];
list l[Smerenie + 1];
u16 stack[Nadejde + 1];
int set[Nadejde / 32 + 1];

void addEdge(int u, int v, int pos) {
  l[pos].v = v;
  l[pos].next = adj[u];
  adj[u] = pos;
}

int getBit(int x) {
  return (set[x >> 5] >> (x & 31)) & 1;
}

void setBit(int x) {
  set[x >> 5] |= 1 << (x & 31);
}

void dfs(int u) {
  int pos;

  if (!getBit(u)) {
    setBit(u);
    for (pos = adj[u]; pos; pos = l[pos].next) {
      dfs(l[pos].v);
    }
    stack[ss++] = u;
  }
}

int main(void) {
  int u, v;
  FILE *f = fopen("sortaret.in", "r");

  /* Citirea datelor. */
  fscanf(f, "%d %d", &N, &M);
  for (; M; M--) {
    fscanf(f, "%d %d", &u, &v);
    addEdge(u, v, M);
  }
  fclose(f);

  /* Calcularea solutiei. */
  for (u = 1; u <= N; u++) {
    dfs(u);
  }

  /* Afisarea solutiei. */
  freopen("sortaret.out", "w", stdout);
  while (ss) {
    fprintf(stdout, "%d ", stack[ss - 1]);
    ss--;
  }
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}