Skip to content

Instantly share code, notes, and snippets.

@arkokoley
Created April 26, 2015 18:05
Show Gist options
  • Save arkokoley/556ebb8b0721d60279d5 to your computer and use it in GitHub Desktop.
Save arkokoley/556ebb8b0721d60279d5 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment