Login

Create Account
Customer Service Chat
+14156709189
info@expertsmind.com
Submit Homework/Assignment
Get quote & make Payment
Get Solution
C++ Data Structure program, C/C++ Programming
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 n1. 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 nondeterminism 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 nondeterminism 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
Explain about the character constants in c language, Explain about the Char...
Explain about the Character Constants in c language? The character constant is a single alphabet and a single digit or a single special symbol enclosed within a pair of single
MCQ, in a multilist organisation
in a multilist organisation
Algorithm and flowcharts, algorithm to find out all the factors of given po...
algorithm to find out all the factors of given positive integers
Define procedure that take argument or return integral value, Simpson's Rul...
Simpson's Rule is a more accurate method of numerical integration than the method described in class. Using Simpson's Rule, the integral of a function f between a and b is approxim
Mat lab programming, MAT LAB programming Project Description: Just fo...
MAT LAB programming Project Description: Just for who are PROFESSIONAL IN MATLAB i have simulation and i would like to simulate the equation in ,and test the all simulatio
Genetic disease, Many human diseases could be controlled by the knowledge o...
Many human diseases could be controlled by the knowledge of the gene’s structure and pattern. The human gene could be represented by four nucleotides. Each nucleotide is represente
C program to display a rectangle, Aim: To implement a program to display a...
Aim: To implement a program to display a rectangle, circle and triangle. Code: class shape { public: vir
Write a function to calculate the exchange rate, Write a function to calcul...
Write a function to calculate the exchange rate of pounds to dollars Answer Td = 2xTp The parameter passed over is the number of pounds and returned the value in do
C++, Write a program to find the area under the curve y = f(x) between x = ...
Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b
C prg, main() { int a[5]={1,3,6,7,0}; int *b; b=&a[2]; } The value of b[1]...
main() { int a[5]={1,3,6,7,0}; int *b; b=&a[2]; } The value of b[1] is
Assignment Help
Accounting Assignment Help
Economics Assignment Help
Finance Assignment Help
Statistics Assignment Help
Physics Assignment Help
Chemistry Assignment Help
Math Assignment Help
Biology Assignment Help
English Assignment Help
Management Assignment Help
Engineering Assignment Help
Programming Assignment Help
Computer Science Assignment Help
ExpertsMind Services
Online Tutoring
Projects Assistance
Exam Preparation
Coursework Help
Programming Help
IT Services
Why Us ?
~Experienced Tutors
~24x7 hrs Support
~Plagiarism Free
~Quality of Work
~Time on Delivery
~Privacy of Work