Cod sursa(job #3199737)

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

const int MAX_NODES = 50'000;

struct node {
  std::vector<int> adj;
  bool seen;
};

node n[MAX_NODES + 1];
std::vector<int> order;
int num_nodes;

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);
    n[u].adj.push_back(v);
  }

  fclose(f);
}

void dfs(int u) {
  if (n[u].seen) {
    return;
  }

  n[u].seen = true;
  for (auto v: n[u].adj) {
    dfs(v);
  }

  order.push_back(u);
}

void dfs_driver() {
  for (int u = 1; u <= num_nodes; u++) {
    dfs(u);
  }
}

void write_order() {
  FILE* f = fopen("sortaret.out", "w");
  for (int i = num_nodes - 1; i >= 0; i--) {
    fprintf(f, "%d ", order[i]);
  }
  fputc('\n', f);
  fclose(f);
}

int main() {
  read_graph();
  dfs_driver();
  write_order();

  return 0;
}