Cod sursa(job #1658498)

Utilizator radu.bRadu Brumariu radu.b Data 21 martie 2016 16:31:08
Problema Sortare topologica Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NMax 50001
#define ALB 0
#define GRI 1
#define NEGRU 2


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

int idx;

int visit(int n, int *visited, int *result, struct node** D);

int main(void) {
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w+", stdout);

  int n,m;
  scanf("%d %d", &n, &m);

  int *visited = calloc(n+1, sizeof(int));
  int *R = malloc(sizeof(int)*n);
  struct node **D = calloc(n+1, sizeof(struct node*));

  memset(visited, 0, n);
  memset(R, 0, n);

  for(; m; m--) {
    int x, y;
    scanf("%d %d", &x, &y);
    struct node *N = calloc(1, sizeof(struct node));
    N->v = y;
    N->next = D[x];
    D[x] = N;
  }

  for(int i = 1; i <= n; i++) {
    visit(i, visited, R, D);
  }

  free(visited);
  for(int i = idx; i; i--) {
    printf("%d ", R[i]);
  }
  printf("\n");

  free(R);
  return 0;
}

int visit(int n, int *visited, int *result, struct node **D) {
  if(visited[n] == NEGRU) return 0;
  if(visited[n] == GRI) {
    printf("**** cycle detected **** \n");
    return -1;
  }
  visited[n] = GRI;
  struct node *p = D[n];
  while(p) {
    int k = p->v;
    if(visited[k] == ALB)
      visit(k, visited, result, D);
    p = p->next;
  }
  visited[n] = NEGRU;
  result[++idx] = n;
  return 0;
}