Question

Java Program

You will be given the source and destination of all the tickets in the form of a map, and you have to print the itinerary from all those tickets.
Note:
The path covered by the tickets is not circular.
Other than the final destination, there is exactly one ticket from every city.
Input: The input will be in the following format:
The first line will be an integer ‘n’ indicating the size of the map containing the source and the destination of all the tickets.
The next ‘n’ lines will be the source and the destination of all the tickets.
Each line represents the source and the destination of each ticket, separated by space.
Output: The output should be in the following format
Print all the names of the cities in the itinerary, separated by a space.
Note:
If you cannot get the start of the itinerary, print 'Invalid'.
If multiple itineraries are possible and if they are also valid, then print the itinerary that is the largest in lexicographical order when the complete itinerary is treated as a string. Refer to the ‘Sample Test case 2’ given below.
Sample test case 1:
Input:
4
Mumbai Indore
Hyderabad Warangal
Indore Hyderabad
Delhi Mumbai
Output:
Delhi Mumbai Indore Hyderabad Warangal Sample test case 2:
Input:
2
abc def
abc deg
Output:
abc deg
Sample test case 3:
Input:
3
abc def
abc deg
deg fgt
Output:
abc deg fgt
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Source {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// get the no of tickets from input
int n = in.nextInt();
// map to store all the tickets
Map tickets = new HashMap();
// Store the source and destination of the tickets to the map "tickets"
for (int i = 0; i < n; i++) {
tickets.put(in.next(), in.next());
in.nextLine();
}
// write your code here
}
}

Answer 1

To print the itinerary from the given tickets, use the Depth First Search (DFS) algorithm. Follow the step-by-step process to visit all the connected cities and print the itinerary.

Step-by-step explanation:

To print the itinerary from the given tickets, you can use Depth First Search (DFS) algorithm. DFS is a graph traversal algorithm that visits all the connected vertices of a graph. In this case, the vertices represent the cities and the edges represent the tickets.

Here is the step-by-step process to print the itinerary:

1. Create a map to store the source and destination of all the tickets.
2. Read the input and store the tickets in the map.
3. Create a visited array to keep track of the visited cities.
4. Start the DFS from the first city in the map.
5. In each recursive call of the DFS, check if the current city is visited or not.
6. If the current city is not visited, mark it as visited and recursively call the DFS for its destination city.
7. Print the current city and continue the DFS until all the cities are visited.

In the end, print the cities in the itinerary separated by a space. If the start of the itinerary is not found or multiple valid itineraries are possible, print 'Invalid' or the largest lexicographical order itinerary, respectively.

Answer 2

Below is the complete Java program for this work.

import java.util.*;

public class Source {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// Get the number of tickets from input

int n = in.nextInt();

// Map to store all the tickets

Map<String, String> tickets = new HashMap<>();

// Store the source and destination of the tickets to the map "tickets"

for (int i = 0; i < n; i++) {

tickets.put(in.next(), in.next());

in.nextLine();

}

// Find the start of the itinerary

String startCity = findStartCity(tickets);

// Print the itinerary

printItinerary(startCity, tickets);

}

// Helper method to find the start city

private static String findStartCity(Map<String, String> tickets) {

Set<String> sources = new HashSet<>(tickets.keySet());

Set<String> destinations = new HashSet<>(tickets.values());

sources.removeAll(destinations);

if (sources.size() == 1) {

return sources.iterator().next();

} else {

return "Invalid";

}

}

// Helper method to print the itinerary

private static void printItinerary(String startCity, Map<String, String> tickets) {

List<String> itinerary = new ArrayList<>();

String currentCity = startCity;

while (currentCity != null) {

itinerary.add(currentCity);

currentCity = tickets.get(currentCity);

}

if (itinerary.size() == 1) {

System.out.println("Invalid");

} else {

for (String city : itinerary) {

System.out.print(city + " ");

}

}

}

}