Cod sursa(job #3199715)

Utilizator cata00Catalin Francu cata00 Data 2 februarie 2024 16:07:43
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>

const int MAX_NODES = 50'000;
const int MAX_EDGES = 100'000;

struct cell {
  int v, next;
};

struct node {
  int adj;
  int in_degree;
};

struct queue {
  int a[MAX_NODES];
  int head, tail;

  void push(int u) {
    a[tail++] = u;
  }

  int pop() {
    return a[head++];
  }

  bool is_empty() {
    return head == tail;
  }
};

cell list[MAX_EDGES + 1];
node n[MAX_NODES + 1];
queue q;
int num_nodes;

void add_edge(int u, int v) {
  static int pos = 0;
  list[++pos] = { v, n[u].adj };
  n[u].adj = pos;
  n[v].in_degree++;
}

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

  fscanf(f, "%d %d", &num_nodes, &num_edges);
  while (num_edges--) {
    fscanf(f, "%d %d", &u, &v);
    add_edge(u, v);
  }

  fclose(f);
}

void bfs() {
  FILE* f = fopen("sortaret.out", "w");

  for (int u = 1; u <= num_nodes; u++) {
    if (!n[u].in_degree) {
      q.push(u);
    }
  }

  while (!q.is_empty()) {
    int u = q.pop();
    fprintf(f, "%d ", u);
    for (int ptr = n[u].adj; ptr; ptr = list[ptr].next) {
      int v = list[ptr].v;
      n[v].in_degree--;
      if (!n[v].in_degree) {
        q.push(v);
      }
    }
  }

  fprintf(f, "\n");
  fclose(f);
}

int main() {
  read_graph();
  bfs();

  return 0;
}