Cod sursa(job #1538308)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 28 noiembrie 2015 19:42:09
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 50000

typedef struct node{
  int data;
  struct node * next;
} node;

node *G[MAX_NODES];
int inDegree[MAX_NODES];
int queue[MAX_NODES], q_curr, q_tail;

void push(int n) {
  queue[q_tail++] = n;
}

int pop() {
  return queue[q_curr++];
}

void add(int from, int to) {
  node * p = malloc(sizeof(node));
  p->data = to;
  p->next = G[from];
  G[from] = p;
}

void readGraph(int m, FILE * in) {
  int i, from, to;

  for (i = 1; i <= m; i++) {
    fscanf(in, "%d %d", &from, &to);
    add(from - 1, to - 1);
    inDegree[to - 1]++;
  }
}

void printTopoSort(int n, FILE *out) {
  int i, curr_node;
  node * adj;

  for (i = 0; i < n; i++) {
    if (!inDegree[i]) {
      push(i);
    }
  }

  while (q_curr < q_tail) {
    curr_node = pop();
    fprintf(out, "%d ", curr_node + 1);
    for (adj = G[curr_node]; adj; adj = adj->next) {
      --inDegree[adj->data];
      if (!inDegree[adj->data]) {
        push(adj->data);
      }
    }
  }
}

int main() {
  FILE * in, * out;
  int m, n;

  in = fopen("sortaret.in", "r");
  fscanf(in, "%d %d", &n, &m);
  readGraph(m, in);
  fclose(in);

  out = fopen("sortaret.out", "w");
  printTopoSort(n, out);
  fclose(out);

  return 0;
}