Description

A long time ago in a galaxy far, far away, the country Mafghanistan had n cities and m old roads, where each road connected a pair of cities. Due to the treacherous mountains, there was no road or even path between some cities (i.e., some cities were unreachable from others). During Operation Mafghanistan Freedom, which spread democracy across Mafghanistan like wildfire in Santa Barbara in the summer, the Mamerican forces evaporated all the old roads in Mafghanistan. As the Commanding General of the Mamerican forces, you are in charge of Operation Mafghan Reconstruction, which will build new roads in Mafghanistan subject to the following constraints:

Due to the treacherous mountains, you may build new roads only between the cities where old roads existed before Operation Mafghanistan Freedom.
You should build enough new roads such that if City A was reachable from City B via some old roads, City A must be reachable from City B via some new roads.
You should minimize the total lengths of the new roads to be built.
Define a region to be a set of cities that will be reachable from one another via some new roads. Find all the regions using algorithms with good asymptotic running times.

You may NOT use STL classes except the string class.

Input

Read input from cin. The input contains the number of cities (n), the number of old roads (m), and a series of old roads where each road is represented by its two terminal cities and its length. Each city is represented by a unique integer from 0 to n-1. Each road length is represented by an integer. The following EBNF specifies the input. An example input is available in the hand out. Your program need not handle invalid input (such as invalid file format or invalid numbers representing cities).

::= *
::= * * ''\n''
::= * * ''\n''
::= * + + * ''\n''
::=
::=
::= +
::= ''0''|''1''|''2''|''3''|''4''|''5''|''6''|''7''|''8''|''9''
::= '' '' | ''\t''
Output

On the first line, print

On the second line, print:

Print each region in the ascending order of the number of cities in the region. For each region:
On the first line, print:

Then, print each new road per line in the ascending order of the lengths of the roads. For each new road, print its two terminal cities represented by their numbers (print the smaller number before the larger number), and then the length of the road, as in the following example:
0 5 10
On the last line, print:

On the last line, print:

The output of your program must match the output of the reference program. In other words, if you run
diff my_output your_output
you should see no output from diff.

Your program must exit with the exit code 0, i.e., call return 0 from the function main() or call exit(0).

Determinism in comparison of equal values

To avoid non-determinism of your algorithm when two roads e1=(s1, t1) and e2=(s2, t2) have the same length, consider e1 to be shorter than e2 if and only if

min(s1, t1) < min(s2, t2), or
min(s1, t1) == min(s2, t2) and max(s1, t1) < max(s2, t2)
To avoid non-determinism of your algorithm when two regions r1={...} and r2={...} have the same number of roads, consider r1 to have fewer roads than r2 if and only if min(r1) < min(r2), where min(s) returns the smallest member of the set s. Note that regions are disjoint sets of cities.

Posted Date: 2/18/2013 6:15:31 AM | Location : United States

Ask an Expert

Related Discussions:- C++ Data Structure program, Assignment Help, Ask Question on C++ Data Structure program, Get Answer, Expert's Help, C++ Data Structure program Discussions

Write discussion on C++ Data Structure program
Your posts are moderated

Write your message here..

Related Questions

Create an array of strings, Create an array of Strings and fill it with som... Create an array of Strings and fill it with some interesting text, such as vacation destinations, album names, or weapon names from a CRPG. Display three elements of the array on t

When do employ "const" reference arguments in function?, A: 1.      By u... A: 1.      By using const protects you against programming errors which inadvertently alter data. 2.      By using const allows function to procedure const and non-const actu

Abstract array - c program, Abstract array - c program: AbstractArray:... Abstract array - c program: AbstractArray::AbstractArray( int anUpper, int aLower, sizeType aDelta ) {     PRECONDITION( anUpper >= aLower );     lastElementIndex = a

Sort wars, Explain each of the algorithms in a way that would be understand... Explain each of the algorithms in a way that would be understandable to an intelligent person who is not familiar with programming. You should not use any code (or even pseudo code

Develop a windows application to show computer hardware, - But with less fe... - But with less features and more user-friendly (particularly for non-tech savvy users). - Software needed having a left menu with links (no pictures required) for every hardwar

Create a program for decision structure , Create the following program or p... Create the following program or propose one of your own. The program must include at least one of each of the following. Decision structure Repetitive structure fu

Define the data types of c language, Define the Data Types of c language? ... Define the Data Types of c language? The C has a concept of 'data types' which are used to define a variable before its use and the definition of a variable will assign storage

Padovan string, padovan string problem program 1 : package test.padovan... padovan string problem program 1 : package test.padovanstring; public class PadovanString {     public int stringOccurrences(int n, String str){        if(n >= 40)

Program to make another type of mask, Write a function that has int paramet... Write a function that has int parameter n, makes another type of mask having n bit 1's from the left most bit and 32- n bit 0's next. The mask is called netmask in this seminar, an

Pebble merchant, 3 kilograms of peebles are needed for converting an area o... 3 kilograms of peebles are needed for converting an area of 1 square meter.the rate of the peeble is 5 per kilogram