10 weeks ago

Rohit • 610

Hyderabad

Question 1

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

2.1 years ago

Gurankit Pal Singh 160

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)

2.1 years ago

Aficion • 0

 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);
}