User Account

All Pages

C++ Data Structure program, C/C++ Programming

Assignment Help:
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.

Related Discussions:- C++ Data Structure program

Puzzles, #questioA Padovan string P(n) for a natural number n is defined as...

#questioA Padovan string P(n) for a natural number n is defined as: P(0) = ‘X’ P(1) = ‘Y’ P(2) = ‘Z’ P(n) = P(n-2) + P(n-3), n>2 where + denotes string concatenation. For a str

Write a program using a friend function, Using a Friend Using a friend ...

Using a Friend Using a friend function is quite easy. The following example explains a friend function to access members of two classes. class Bclass;

201 it, overload assignment opertor to assign the data of one object to ant...

overload assignment opertor to assign the data of one object to anthor

#compiler design limiting instrutions, Ravi is a newbie to the programming ...

Ravi is a newbie to the programming and while learning the programming language he came to know the following rules: · Each program must start with ''''''''{'''''''' and end wi

Write a program of inline function, Here is a program that uses an inline f...

Here is a program that uses an inline function to compute and return the absolute value of its input argument. # include inline int abs(int x) {                  ret

I need csgo wallhack and human aimbot, I need CSGO Wallhack and Human Aimbo...

I need CSGO Wallhack and Human Aimbot Project Description: Need a CSGO hack which can ESP Wallhack and Aimbot realistically. Must be VAC Proof, and ESL proof, as wel

Described friend?, A: Something to let your class to grant access to anothe...

A: Something to let your class to grant access to another class or function. Friends may be either classes or functions. Class grants access privileges to its friends. In genera

Write a program that predicts users age, Write a program that predicts user...

Write a program that predicts users age: Write a program that predicts users' age (0-128 years old) with at most 7 questions. The game starts with asking the user whether he/s

Fraction coding, Create a program that asks the user for two integers which...

Create a program that asks the user for two integers which represent the numerator and denominator parts of fraction. Print out a simplification of the fraction. Example: Enter th

FlipFlaps fltk project, The project is to design and write a C++11/FLTKgame...

The project is to design and write a C++11/FLTKgame program with a graphical user interface.The game is based on "pancake sorting," as described at http://en.wikipedia.org/wiki/P

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd