Cod sursa(job #1700152)

Utilizator TincaMateiTinca Matei TincaMatei Data 9 mai 2016 18:08:57
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>
#define MAX_NODURI 50000
#define MAX_MUCHII 100000

int first[1+MAX_NODURI];
int last[1+MAX_NODURI];
int muchie[1+MAX_MUCHII];
int next[1+MAX_MUCHII];
char fol[1+MAX_NODURI];
int rez[MAX_NODURI];
int intrare[1+MAX_NODURI];
int top;

void solve(int n) {
  int i;
  i = first[n];
  while(i != 0) {
    if(!fol[muchie[i]])
      solve(muchie[i]);
    i = next[i];
  }
  rez[top] = n;
  top++;
  fol[n] = 1;
}

int main() {
  int n, m, i, a, b;
  FILE *fin = fopen("sortaret.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(i = 1; i <= m; i++) {
    fscanf(fin, "%d%d", &a, &b);
    if(first[a] == 0)
      first[a] = last[a] = i;
    else
      last[a] = next[last[a]] = i;
    muchie[i] = b;
    intrare[b]++;
  }
  fclose( fin );

  i = 1;
  while(intrare[i] > 0)
    i++;
  solve(i);
  FILE *fout = fopen("sortaret.out", "w");
  for(i = top - 1; i >= 0; i--)
    fprintf(fout, "%d ", rez[i]);
  fclose( fout );
  return 0;
}