Cod sursa(job #1699897)

Utilizator madalina41724Madalina Marin madalina41724 Data 8 mai 2016 19:37:29
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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 = malloc(sizeof(int)*n);
  int *R = malloc(sizeof(int)*n);
  struct node *D = malloc(sizeof(struct node) * n);

  for(int i = 0; i <= n; i++) {
    D[i].v = i;
    D[i].next = NULL;
  }
  memset(visited, 0, n);
  memset(R, 0, n);

  for(int i = 0; i < m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    struct node *N = malloc(sizeof(struct node));
    N->v = y;
    N->next = D[x].next;
    D[x].next = 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].next;
  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;
}