In this program you will work with graphs. The input to the program is an undirected graph in adjacency list format. To store the graph, you should set up an array G, so that G[i]) is a pointer to a linked list storing vertices adjacent to vertex i. Your program must output the degrees of vertices in the sorted order. You must use bucket sorting for sorting degrees, and have an array Bucket of pointers in your program so that Bucket[i] points to a linked list containing all vertices that have degree i. You should not use STL for this assignment. Note that time complexity of your program should be O(n+m), where n is number of vertices, and m is number of edges.
Your program should read from a file and write to file. The input file will contain multiple data sets, separated by one blank line. You program must output the degrees of each graph in one line. Your program must work on graphs of up to 1000 vertices.
Input example:
1 2
2 1 3
3 2
------------
1 2 3
2 1 3
3 2 1
---------
1 2
2 1
3 4
4 3
Output example:
Sorted degrees for graph one is:1,1,2
Sorted degrees for graph two are: 2,2,2
Sorted degrees for graph three are:1,1,1,1