Time limit: 5000ms
Memory limit: 256mb

Description (Required):

This exercise is similar to "Depth-First Search 2022 (Optional)" but in a BFS manner.

There is an undirected connected graph. You need to store all edges in adjacency list and traverse the graph in a BFS manner. Suppose there are 100 nodes at most.

In this exercise, you are required to fulfill the following two tasks.

1. Construct an adjacency list.
Same to ex1.
Initially, the adjacency list is empty. Then given a sequence of distinct edges (a,b), you need to insert them into the adjacency list one by one. Note that for every edge (a,b), you need insert both (a,b) and (b,a). And for the edges from same out-node, their in-nodes stored in adjacency list are in decreasing order.

2. Output nodes in BFS manner.
We have defined the order of edges in task 1, So we have an unique result of BFS. We always start from node 0 to traverse the graph. In BFS, there needs a queue to store the order of nodes we have visited and want to visit their neighbors. The function of queue is provided. 

The main function has been provided. It first asks the user to input the total edges number m, and input all these edges to construct the adjacency list. Then it invokes the function bfs to output each node. 

You need to complete two functions.

void insert(int v1, int v2);// same to ex1

void bfs(int v);

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

Sample Output 1:
Input the number of edges:
Input these edges:
0 5 4 3 2 1 

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

Sample Output 2:
Input the number of edges:
Input these edges:
0 2 1 6 5 4 3 7 


Code Template:

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

#define MAX_NODES 100

typedef struct _adjlist {
     int node;
     struct _adjlist *link;
} adjlist;

typedef struct {
  int size;
  int last; 
  int *elements;
} queue;

queue* createQ(int size)
{
  queue *q;
  q = (queue*)malloc(sizeof(queue));
  q->size = size;
  q->elements = (int*)malloc(size * sizeof(int));
  q->last = -1;
  return q;
}

int IsEmptyQ(queue *q){
  if (q->last == -1) return 1;
  else return 0;
}

int IsFullQ(queue *q){
  if (q->last == q->size - 1) return 1;
  else return 0;
}


void enqueue(queue *q, int e){
  if (!IsFullQ(q)) {  
	q->last++; 
	q->elements[q->last] = e;
  } 
  else  printf("Error\n");
}

int dequeue(queue *q){
  int i, j;
  if (!IsEmptyQ(q)) { 
    i = q->elements[0];
    for (j = 1; j <= q->last; j++) 
	q->elements[j-1] = q->elements[j];
    q->last--;
    return i;
   } else  printf("Error\n");
}



adjlist graph[MAX_NODES]; 

int visited[MAX_NODES];    // 0-unvisited    1-visited

void insert(int v1, int v2);

void bfs(int v);



void insert(int v1, int v2)
{
    /*
	insert edge (v1,v2) into adajacency list.
	Note order!
        Fill in your code here...
    */
}

void bfs(int v)
{
    /*
        Fill in your code here...
        visit v and store his unvisited neighbor into queue..
    */
}

int main()
{
    int m,a,b;
    
    // initialize
    for(int i=0;i<MAX_NODES;i++)
    {
	graph[i].link=NULL;
	visited[i]=0;  // unvisited 
    }


    printf("Input the number of edges:\n");
    scanf("%d",&m);
    printf("Input these edges:\n");
    for(int i=0; i<m; i++)
    {
        scanf("%d %d", &a, &b);
        insert(a,b);
	  insert(b,a);
    }
    if( m > 0){
        bfs(0);
    }
    return 0;
}