Cod sursa(job #2671635)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 12 noiembrie 2020 14:41:33
Problema Sortare topologica Scor 80
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <ctype.h>

#define MAXN 50000
#define MAXM 100000
#define NIL -1

FILE *fin, *fout;

int viz[MAXN];
int list[MAXN];
int nrpar[MAXN];
int node[MAXM];
int next[MAXN];

int rez[MAXN];
int rp;

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit(ch = fgetc(fin)) );
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n;
}

void dfs( int root ){
  int cc = list[root], child;// cc = child cell

  viz[root] = 1;

  while( cc != NIL ){
    child = node[cc];
    if( !viz[child] )
      dfs(child);
    
    cc = next[cc];
  }

  rez[--rp] = root;
}

int main(){
  fin  = fopen("sortaret.in",  "r");
  fout = fopen("sortaret.out", "w");

  int n, m, i, a, b;

  n = fgetint();
  for( i = 0 ; i < n ; i++ )
    list[i] = NIL;
  
  m = fgetint();
  for( i = 0 ; i < m ; i++ ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    node[i] = b;
    next[i] = list[a];
    list[a] = i;
    nrpar[b]++;
  }

  rp = n;
  for( i = 0 ; i < n ; i++ )// amortizat O(N)
    if( nrpar[i] == 0 )
      dfs(i);

  for( i = 0 ; i < n ; i++ )
    fprintf(fout, "%d ", rez[i] + 1);
  fputc('\n', fout);

  fclose(fin);
  fclose(fout);
  return 0;
}