Cod sursa(job #3204054)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 15 februarie 2024 15:47:54
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define SIZE 100000

int pred[SIZE];
vector<int> succ[SIZE];
queue<int> que;

int main() {
  FILE *fin, *fout;
  int n, m;
  int a, b;
  int i, x;

  fin = fopen("sortaret.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf(fin, "%d%d", &a, &b);
    succ[a].push_back(b);
    pred[b]++;
  }

  fclose(fin);

  fout = fopen("sortaret.out", "w");

  for (i = 1; i <= n; i++)
    if (pred[i] == 0) {
      que.push(i);
    }

  while (!que.empty()) {
    x = que.front();
    fprintf(fout, "%d ", x);
    que.pop();
    for (int y : succ[x]) {
      pred[y]--;
      if (pred[y] == 0)
        que.push(y);
    }
  }

  fclose(fout);

  return 0;
}