Problem 1050 Title: Flight Travel Planner Description You are working for a trav
ID: 3678467 • Letter: P
Question
Problem 1050
Title: Flight Travel Planner
Description
You are working for a travel agency and are asked to write a computer program that can provide travel
advice between cities based on a given map. The first line of the input of the program contains one integer n.
n (2<=n<=10000) is the number of cities on the map. The second line of the input also contains an integer,
m, (2<=m<=10000), which indicates the number of connections that will follow in the input below. Then,
starting from the third line of the input, each line contains two integers from 1 to n, i.e. the connections
between the cities. If a line says "a b", then it means that there is direct flight between city a and city b.
There will be m of such connections. The last line also contains a pair of cities, say "c d", which will
represent a query: "is there a connecting flight between c and d?"
Here is one sample input:
6
7
6 4
3 4
5 4
3 2
5 2
5 1
2 1
1 6
This sample input can be visualized as follows:
For this flight network, there exists at least one route between every pair of cities. For example, between city
5 and 6, there exists a route with 1 stop at city 4.
Given the input and the query, answer whether there is a route between cities c and d (note that this
connection can be indirect). The output should be "Yes" or "No".
Let x be the total number of lines of the input. We know for sure that x is much smaller than n square. Your
implementation should take this into consideration (for the purpose of saving memory).
For example, let us consider the case with n=10000 and x=10000 (so x is much less than n square). One easy
way to represent a graph in memory is to use a n by n matrix. If the element in the i-th row and the j-th
column equals 1, then that means node i and j are directly connected (0 means not directly connected). The
memory consumption of the matrix representation is at least n square over 2 bits (each element only needs 1
bit; also, we only need to store half of the matrix due to symmetry). When n=10000, n square over 2 bits is
just too much. You should find better ways to represent graphs in memory.
Input
Flight network
Output
Yes or No
Sample Input
6
7
6 4
3 4
5 4
3 2
5 2
5 1
2 1
1 6
Sample Output
Yes
Explanation / Answer
#include <iostream>
#include <list>
#include <queue>
using namespace std;
/*
* Class Declaration
*/
class Graph
{
private:
int V;
list<int> *adj;
public:
Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int w);
void BFS(int s, bool visited[]);
Graph getTranspose();
bool isConnected();
};
/*
* Add Edge to connect v and w
*/
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
/*
* A recursive function to print BFS starting from s
*/
void Graph::BFS(int s, bool visited[])
{
list<int> q;
list<int>::iterator i;
visited[s] = true;
q.push_back(s);
while (!q.empty())
{
s = q.front();
q.pop_front();
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
q.push_back(*i);
}
}
}
}
/*
* Function that returns reverse (or transpose) of this graph
*/
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
/*
* Check if Graph is Connected
*/
bool Graph::isConnected()
{
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
BFS(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.BFS(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
/*
* Main Contains Menu
*/
int main()
{
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 3);
if (g.isConnected())
cout<<"The Graph is Connected"<<endl;
else
cout<<"The Graph is not Connected"<<endl;
Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
if (g1.isConnected())
cout<<"yes,The Graph is Connected"<<endl;
else
cout<<"No,The Graph is not Connected"<<endl;
return 0;
}
if you want to read from command prompt you need to ask values using cin function in an array
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.