I had a homework assignment in my cs3050 last week, that I was having trouble with what should be the easiest part.
The homework looked like this:
In this program you will read a file specifying an undirected graph as a list of edges and output the number of connected components as well as the size (number of vertices) of the smallest component. The number of vertices is given on the first line of the input. The vertices are numbered in order from 1 to the total number of vertices. The rest of the input file simply lists the edges in arbitrary order as pairs of vertices, with each edge on a separate line. For example for the following input:
The output is:
The number of connected components is 3
The smallest component has
I had trouble setting up the adjacency list. I knew that I could just use breadths first search or depths first search once I had it, but I have always had trouble with allocating memory. I didn't end up figuring it out before it was due, but I know we are going to be having more like this.
All I need to know is how to get it all into the adjacency list and then I know what to do from there.