dfs.c

#include<stdio.h>
#include<stdlib.h>

typedef struct gnode{
  int val;
  char color;
} node;

typedef struct queue{
  node *element;
  struct queue *next;
} queue;

int changeColor(node *n, char color){
  n->color = color;
}

int EQ(node *n, queue **head, queue **rear){
  queue *q = malloc(sizeof(struct queue));
  q->element = n;
  q->next= NULL;
  if((*rear)!=NULL)
    (*rear)->next = q;
  *rear = q;
  if(*head==NULL)
    *head = q;
  return 0;
}

node *DQ(queue **head, queue **rear){
  queue *d = *head;
  struct gnode *x = (*head)->element;//->val;
  if(*head!=NULL)
    *head = (*head)->next;
  free(d);
  if(*head == NULL)
    *rear = NULL;
  return x;
}

int push(node *n, queue **head){
  queue *q = malloc(sizeof(queue));
  q->element = n;
  q->next = *head;
  *head = q;
  return 0;
}

node *pop(queue **head){
  if(*head == NULL)
    return NULL;
  node *n = (*head)->element;
  queue *p = *head;
  *head = (*head)->next;
  free(p);
  return n;
}

int main(int argc, char *argv[]){
  FILE *file = fopen(argv[1],"r");
  int i,u,v,N;
  fscanf(file,"%d\n",&N);
  node **n = malloc(sizeof(node*)*N);
  for(i=0;i<N;++i){
    n[i] = malloc(sizeof(node));
    n[i]->val = i+1;
    n[i]->color = 'R';
  }
  queue *head=NULL, *lhead=NULL, *lrear=NULL;
  queue **ehead = (queue **)malloc(sizeof(queue*)*N), **erear = (queue**)malloc(sizeof(queue*)*N);
  queue *s = malloc(sizeof(queue));
  for(i=0;i<N;++i){
    ehead[i] = erear[i] = NULL;
  }
  while(!feof(file)){
    fscanf(file,"%d %d \n",&u, &v);
    EQ(n[v-1],&ehead[u-1],&erear[u-1]);
    if(feof(file))
      break;
  }
  push(n[0],&head);
  while(ehead[0]!=NULL){
    node *u = ehead[0]->element;
    ehead[0] = ehead[0]->next;
    if(u->color=='R'){
      push(u,&head);
      changeColor(u,'Y');
    }
  }
  while(head!=NULL){
    node *element = pop(&head);
    changeColor(element,'B');
    EQ(element,&lhead,&lrear);
    int e = element->val;
    while(ehead[e-1]!=NULL){
      node *u = ehead[e-1]->element;
      ehead[e-1] = ehead[e-1]->next;
      if(u->color=='R'){
        push(u,&head);
        changeColor(u,'Y');
      }
    }
  }
  while(lhead!=NULL){
    printf("%d->",lhead->element->val);
    lhead = lhead->next;
  }
  fclose(file);
  return 0;
}