Noah is a traveler who wants to travel to different places. He knows the paths between various cities. But here's a catch, he wants to travel in a unique pattern between various cities. Since he's having a hard time choosing the path he wants to travel, he has decided that starting from the first city he'll move to the next city which comes first in the list. After visiting the cities connected to a particular city, he moves on to the next city in the list and repeats the same.
Given the number of paths and the next cities, print the order in which Noah has to travel.
Input Format
Output Format
The output consists of a single string in each line which denotes the path the traveler has to travel
Only print the cities which are connected
Note: s1 to s2 denotes a path from City A to City B but NOT from city B to city A
Evaluation Parameters
Sample Input
5
Bangalore Hyderabad
Bangalore Chennai
Hyderabad Mumbai
Hyderabad Delhi
Chennai Kerala
Bangalore
Sample Output
Bangalore
Hyderabad
Chennai
Mumbai
Delhi
Kerala
This problem can be solved using bfs. Simply store the cities in the adjacency list, and also store the order of the cities in a list. Then iterate through the list, and if a city is not visited, then apply bfs on that city.
bfs(queue, graph, vis, ans)
while queue is not empty
city=queue.front
queue.pop
if city is not visited
vis[city]=true
ans.append(city)
for neighbor in graph[city]]
if neighbor is not visited
queue.push(neighbour)
main()
queue.append(firstCity)
bfs(queue, graph, vis, ans)
for city in cities:
if city is not visited
bfs(queue, graph, vis, ans)
class Solution{
public:
map<string, vector<string>> adj;
void insert(vector<string> from, vector<string> to){
int n = from.size();
for(int i = 0; i < n; i++){
adj[from[i]].push_back(to[i]);
}
}
set<string> vis;
void bfs(string start){
queue<string> Q; Q.push(start);
vis.insert(start);
while(!Q.empty()){
string front = Q.front();
Q.pop();
cout << front << endl;
for(int i = 0; i < adj[front].size(); i++){
string child = adj[front][i];
if(!vis.count(child)){
Q.push(child);
vis.insert(child);
}
}
}
}
};
int main(){
vector<string> from{"Bangalore", "Bangalore", "Hyderabad", "Hyderabad", "Chennai"};
vector<string> to{"Hyderabad", "Chennai", "Mumbai", "Delhi", "Kerala"};
string start = "Bangalore";
Solution Noah;
Noah.insert(from, to);
Noah.bfs(start);
}