Question: Navi, Previously asked On-Campus Question in IITs, 2022 | The Traveler
0
Entering edit mode

Question 1

Click here to Practice

The Traveler

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

  • The first line is an integer which denotes the number of paths P
  • The next P lines take two space separated strings s1 and s2
  • The last line after P lines takes a single string as input which denotes the city the traveler visits first

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
ADD COMMENTlink 2.1 years ago Rohit • 600
2
Entering edit mode

Solution of Question 1

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.

Pseudo Code:

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)
ADD COMMENTlink 2.0 years ago Gurankit Pal Singh 160
0
Entering edit mode
 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);
}
ADD COMMENTlink 2.0 years ago Aficion • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts