Time limit: 5000ms
Memory limit: 256mb

Description:
There is an undirected connected graph, and you need to traverse the graph in a BFS manner using the implemented adjacency list. Suppose there are at most 100 nodes (with ID in the range 0-99).

In this exercise, you are required to find a shortest path from vertex 0 to vertex t by using BFS. When doing BFS, visit the out-neighbors of a vertex in ascending order of their node IDs.

The main function is already provided. It reads the input edges, constructs the adjacency list of the graph, invokes the bfs function, and displays the shortest path from vertex 0 to vertex t.

Input Format:
The first line contains three numbers: the number of vertices n, the number of edges m, and the ID of the destination vertex t.
The next m lines represent m edges. Note that the graph in this problem is undirected.

You need to complete one function: void bfs(int v);

Sample Input 1:
6 6 3
1 4
5 2
3 5
0 4
5 0
5 4

Sample Output 1:
0 5 3

Sample Input 2:
8 10 7
0 1
0 2
1 3
1 4
3 7
4 7
2 5
2 6
5 7
6 7

Sample Output 2:
0 1 3 7


Code Template:

/*
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

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

#define MAX_NODES 100

typedef struct list_node list_Node;

struct list_node {
  int id;
  list_Node *next;
  list_Node *prev;
};

typedef struct linked_list List;

struct linked_list {
  list_Node *head;
  list_Node *tail;
};

struct Queue {
  int *arr;
  int capacity;
  int front;
  int rear;
};

struct Queue *CreateQ(int capacity) {
  struct Queue *queue = (struct Queue *)malloc(sizeof(struct Queue));
  queue->arr = (int *)malloc(sizeof(int) * capacity);
  queue->capacity = capacity;
  queue->front = 0;
  queue->rear = 0;
  return queue;
}

int IsFullQ(struct Queue *queue) {
  return queue->front == (queue->rear + 1) % queue->capacity;
}

int IsEmptyQ(struct Queue *queue) { return queue->front == queue->rear; }

void enqueue(struct Queue *queue, int x) {
  if (IsFullQ(queue)) {
    printf("Queue is full\n");
  } else {
    queue->arr[queue->rear] = x;
    queue->rear = (queue->rear + 1) % queue->capacity;
  }
}

int dequeue(struct Queue *queue) {
  if (IsEmptyQ(queue)) {
    printf("Queue is empty\n");
    return -1;
  } else {
    int e = queue->arr[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    return e;
  }
}

List *graph[MAX_NODES];

int color[MAX_NODES];
int prevArray[MAX_NODES];

void insert(int v1, int v2);

void bfs(int v);

List *create_List() {
  List *L;
  L = (List *)malloc(sizeof(struct linked_list));
  L->head = (list_Node *)malloc(sizeof(list_Node));
  L->head->prev = NULL;
  L->tail = (list_Node *)malloc(sizeof(list_Node));
  L->head->next = L->tail;
  L->tail->prev = L->head;
  L->tail->next = NULL;
  return L;
}

void display_list(List *L) {
  list_Node *curr = L->head->next;
  while (curr != L->tail) {
    printf("%d ", curr->id);
    curr = curr->next;
  }
  printf("\n");
}

void display_graph(int numVertex) {
  for (int i = 0; i < numVertex; i++) {
    printf("i = %d: ", i);
    display_list(graph[i]);
  }
}

// Insert a node with Element e at the head of the linked list
void insert_list_node(List *L, int v) {
  list_Node *node = (list_Node *)malloc(sizeof(list_Node));
  node->id = v;
  node->next = L->head->next;
  node->next->prev = node;
  node->prev = L->head;
  L->head->next = node;
}

void insert_edge(int v1, int v2) {
  // insert v2 into the linked list graph[v1], meanwhile keeping it in ascending
  // order

  list_Node *new_node = (list_Node *)malloc(sizeof(list_Node));
  new_node->id = v2;

  List *L = graph[v1];
  list_Node *curr = L->head->next;
  while (curr != L->tail) {
    if (curr->id < v2) {
      curr = curr->next;
    } else {
      break;
    }
  }

  // insert the new node before the curr position
  new_node->next = curr;
  new_node->prev = curr->prev;
  curr->prev = new_node;
  new_node->prev->next = new_node;

  return;
}

void bfs(int v) {
  for (int i = 0; i < MAX_NODES; i++) {
    color[i] = 0;
    prevArray[i] = -1;
  }
  /*
  Fill in your code here...
  visit v and store his unvisited neighbor into queue..
  */
  return;
}

void display_shortest_path(int t, int prevArray[]) {
  List *L = create_List();
  insert_list_node(L, t);
  int prev = prevArray[t];

  while (prev != -1) {
    insert_list_node(L, prev);
    prev = prevArray[prev];
  }

  list_Node *tmp = L->head->next;
  while (tmp != L->tail) {
    printf("%d", tmp->id);
    tmp = tmp->next;
    if (tmp != L->tail) {
      printf(" ");
    } else {
      printf("\n");
    }
  }
}

int main() {
  int n, m, t, a, b;
  scanf("%d%d%d", &n, &m, &t);

  for (int i = 0; i < n; i++) {
    graph[i] = create_List();
  }

  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    insert_edge(a, b);
    insert_edge(b, a);
  }

  bfs(0);
  display_shortest_path(t, prevArray);

  return 0;
}