Programming Homework Help

Input: The input is an undirected, weighted graph given in a plain text file in the following format: the first line contains just the number of vertices (which are assumed to be labeled with the numbers 1 up to the number of vertices), and then the endpoints of the edges are listed followed by the weight of the edge in each line (you may assume that the weights are integers and that the graph is simple).

Output: The program should print (in complete English sentences) the weight of a minimum weight edge-cut, then specify the edge-cut by listing the vertices on one side, then list the edges of the edge-cut with their respective weights. (Print into a file.)

Ideally use something like Farger’s Algorithm or Stoer-Wagner.