Cod sursa(job #1455319)

Utilizator cella.florescuCella Florescu cella.florescu Data 27 iunie 2015 15:51:39
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
#define MAXM 100000
int lst[MAXN+1], vf[MAXM+1], urm[MAXM+1], sol[MAXN], m, n;
char viz[MAXN+1];

inline void adauga(int x, int y){
  vf[++m]=y;
  urm[m]=lst[x];
  lst[x]=m;
}

void dfs(int nod){
  int p;
  viz[nod]=1;
  p=lst[nod];
  while(p){
    if(viz[vf[p]]==0)
      dfs(vf[p]);
    p=urm[p];
  }
  sol[n++]=nod;
}

int main()
{
    FILE *fin, *fout;
    int N, M, i, x, y;
    fin=fopen("sortaret.in", "r");
    fscanf(fin, "%d%d", &N, &M);
    for(i=0; i<M; i++){
      fscanf(fin, "%d%d", &x, &y);
      adauga(x, y);
    }
    fclose(fin);
    for(i=1; i<=N; i++)
      if(viz[i]==0)
        dfs(i);
    fout=fopen("sortaret.out", "w");
    for(i=n-1; i>=0; i--)
      fprintf(fout, "%d ", sol[i]);
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}