DESCRIPTION
Problem Statement
Noah is a traveller who wants to travel to different places. He knows in a unique pattern 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 (s1) he’ll move to the next city which is closest to it (s2) and then he’ll move to the next city closest to it and so on.
Given the number of paths and the closest cities, print the order in
which Noah has to travel. Assume that the city which comes first (last
line of Input) is closest to him.
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 traveller visits first
Constraints
• 1 <= P <= 100
1<= length of each string <= 100
Output Format
• The output consists of a single string in each line which denotes
the path the traveller has to travel
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
Mumbai
Delhi
Chennai
Kerala
EXECUTION TIME LIMIT
2 seconds
2 Likes
The question seems a bit unclear. For the given sample TC I don’t understand how Delhi
comes after Bangalore, Hyderabad, Mumbai
especially because the paths are unidirectional !!
1 Like
It is a simple preorder DFS question but instead of integer input edges we take string input edges like their is a edge between Bangalore and Hyderabad.
I don’t know how to solve it with string input edges.
If you know please provide the solution.
Hope now you will understand the question.
@darshancool25
It is a simple preorder DFS question but instead of integer input edges we take string input edges like their is a edge between Bangalore and Hyderabad.
I don’t know how to solve it with string input edges.
If you know please provide the solution.
Hope now you will understand the question
@darshancool25 @yatintripathi Please give the solution here.
Hi @yatintripathi , do have a look, I hope it covers all test cases
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class SpringWorks {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int path = sc.nextInt();
List <List<String>> paths = new ArrayList<>();
while(path > 0) {
String temp[] = new String[2];
temp[0] = sc.next();
temp[1] = sc.next();
paths.add(Arrays.asList(temp));
path--;
}
String src = sc.next();
List<String> output = getPaths(paths, src);
System.out.println(output);
sc.close();
}
private static List<String> getPaths(List<List<String>> paths, String src) {
Map<String, ArrayList<String>> adjList = new HashMap<>();
Set<String> lnkSet = new HashSet<>();
paths.forEach((p) -> {
String s = p.get(0);
String d = p.get(1);
if(adjList.containsKey(s)) {
adjList.get(s).add(d);
} else {
ArrayList<String> t = new ArrayList<>();
t.add(d);
adjList.put(s, t);
}
if(!lnkSet.contains(s)) lnkSet.add(s);
if(!lnkSet.contains(d)) lnkSet.add(d);
});
List<String> result = new ArrayList<>();
if(!lnkSet.contains(src)) return result;
ArrayList<String> P = new ArrayList<>(lnkSet);
Boolean[] visited = new Boolean[P.size()];
Arrays.fill(visited, false);
dfs(adjList, P, visited,src, result);
return result;
}
private static void dfs(Map<String, ArrayList<String>> adjList, ArrayList<String> P, Boolean[] visited,
String src, List<String> result) {
int index = P.indexOf(src);
visited[index] = true;
result.add(src);
ArrayList<String> nodes = adjList.get(src);
if(nodes == null) return;
for(String k : nodes) {
int idx = P.indexOf(k);
if(!visited[idx]) {
dfs(adjList, P, visited, k, result);
}
}
}
}
output : [Bangalore, Hyderabad, Mumbai, Delhi, Chennai, Kerala]