Cod sursa(job #1387128)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 13 martie 2015 18:42:57
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX 50000

struct graphVertex {
  int node;
  struct graphVertex *next;
};

struct graphVertex *GraphList[MAX];
int nodes, vertexNum;
int stiva[MAX];

int visited[MAX];
int L = 0;

void add(int source, int target) {
  struct graphVertex *p = malloc(sizeof(struct graphVertex));
  p -> node = target - 1;
  p -> next = GraphList[source - 1];
  GraphList[source - 1] = p;
}

void readGraph(FILE *in) {
  fscanf(in, "%d %d", &nodes, &vertexNum);

  int i, a, b;
  for (i = 1; i <= vertexNum; i++) {
    fscanf(in, "%d %d", &a, &b);
    add(a, b);
  }
}

void DFS(int node) {
  visited[node] = 1;
  struct graphVertex *p;
  for (p = GraphList[node]; p != NULL; p = p -> next) {
    if (!visited[p -> node]) {
      DFS(p -> node);
    }
  }
  stiva[L++] = node;
}

void printSolution(FILE *out) {
  int i;
  for (i = L - 1; i >= 0; i--) {
    fprintf(out, "%d ", stiva[i] + 1);
  }
}

int main() {

  FILE *in  = fopen("sortaret.in", "r");
  FILE *out = fopen("sortaret.out", "w");

  readGraph(in);
  DFS(0);
  printSolution(out);

  fclose(in);
  fclose(out);

  return 0;
}