Cod sursa(job #1478522)

Utilizator ConsstantinTabacu Raul Consstantin Data 28 august 2015 20:53:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <list>
using namespace std;
#define IN_FILE_NAME "sortaret.in"
#define OUT_FILE_NAME "sortaret.out"
#define NMAX 50001
FILE *in, *out;
int inEdges[NMAX];
list<int> edges[NMAX];
char viz[NMAX];
int N,M;
void read() {
  fscanf(in, "%d %d", &N,&M);
  int inNode, outNode;
  for (int i = 0 ; i < M; i++) {
    fscanf(in, "%d %d", &inNode, &outNode);
    inEdges[outNode]++;
    edges[inNode].push_back(outNode);
  }
}

void walk(int node) {
  viz[node] = 1;
  fprintf(out, "%d ", node);
  for(list<int>::const_iterator i = edges[node].begin();
    i != edges[node].end(); i++) {
      inEdges[*i]--;
      if (inEdges[*i] == 0) {
        walk(*i);
      }
    }
}

void solve() {
  for (int i = 1 ; i <= N ; i++) {
    if (inEdges[i] == 0 && !viz[i]) {
      walk(i);
    }
  }
}

int main() {
  in = fopen(IN_FILE_NAME, "r");
  out = fopen(OUT_FILE_NAME, "w");
  read();
  solve();

  fclose(in);
  fclose(out);
  return 0;
}