Рубрики

Найти маршрут по заданному списку билетов

По заданному списку билетов найдите маршрут в указанном списке.

Пример:

Input:
"Chennai" -> "Banglore"
"Bombay" -> "Delhi"
"Goa"    -> "Chennai"
"Delhi"  -> "Goa"

Output: 
Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,

Можно предположить, что входной список билетов не является циклическим, и существует один билет от каждого города, кроме конечного пункта назначения.

Одним из решений является построение графа и его топологическая сортировка . Временная сложность этого решения составляет O (n).

Мы также можем использовать хеширование, чтобы избежать построения графика. Идея состоит в том, чтобы сначала найти отправную точку. Отправной точкой никогда не будет «на стороне» билета. Как только мы находим начальную точку, мы можем просто пройти заданную карту, чтобы напечатать маршрут по порядку. Ниже приведены шаги.

1) Create a HashMap of given pair of tickets.  Let the created 
   HashMap be 'dataset'. Every entry of 'dataset' is of the form 
   "from->to" like "Chennai" -> "Banglore"

2) Find the starting point of itinerary.
     a) Create a reverse HashMap.  Let the reverse be 'reverseMap'
        Entries of 'reverseMap' are of the form "to->form". 
        Following is 'reverseMap' for above example.
        "Banglore"-> "Chennai" 
        "Delhi"   -> "Bombay" 
        "Chennai" -> "Goa"
        "Goa"     ->  "Delhi"
 
     b) Traverse 'dataset'.  For every key of dataset, check if it
        is there in 'reverseMap'.  If a key is not present, then we 
        found the starting point. In the above example, "Bombay" is
        starting point.

3) Start from above found starting point and traverse the 'dataset' 
   to print itinerary.

Все вышеперечисленные этапы требуют времени O (n), поэтому общая сложность времени составляет O (n).

Ниже приведена реализация вышеуказанной идеи на Java.

Джава

// Java программа для печати маршрута по порядку

import java.util.HashMap;

import java.util.Map;

  

public class printItinerary

{

    // Функция драйвера

    public static void main(String[] args)

    {

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

        dataSet.put("Chennai", "Banglore");

        dataSet.put("Bombay", "Delhi");

        dataSet.put("Goa", "Chennai");

        dataSet.put("Delhi", "Goa");

  

        printResult(dataSet);

    }

  

    // Эта функция заполняет 'result' для данного входного набора данных '

    private static void printResult(Map<String, String> dataSet)

    {

        // Для сохранения реверса данной карты

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

  

        // Чтобы заполнить обратную карту, итерацию по данной карте

        for (Map.Entry<String,String> entry: dataSet.entrySet())

            reverseMap.put(entry.getValue(), entry.getKey());

  

        // Находим начальную точку маршрута

        String start = null;

        for (Map.Entry<String,String> entry: dataSet.entrySet())

        {

              if (!reverseMap.containsKey(entry.getKey()))

              {

                   start = entry.getKey();

                   break;

              }

        }

  

        // Если мы не смогли найти отправную точку, значит что-то не так

        // с вводом

        if (start == null)

        {

           System.out.println("Invalid Input");

           return;

        }

  

        // Как только у нас есть отправная точка, нам просто нужно идти дальше, дальше

        // следующего использования данной хэш-карты

        String to = dataSet.get(start);

        while (to != null)

        {

            System.out.print(start +  "->" + to + ", ");

            start = to;

            to = dataSet.get(to);

        }

    }

}

C ++

#include <iostream>
#include <map>
#include <string>

using namespace std;

  

void printItinerary(map<string, string> dataSet)

{

    // Для сохранения реверса данной карты

    map<string, string> reversemap;

    map<string, string>::iterator it;

  

    // Чтобы заполнить обратную карту, итерацию по данной карте

    for (it = dataSet.begin(); it!=dataSet.end(); it++)

        reversemap[it->second] = it->first;

  

    // Находим начальную точку маршрута

    string start;

  

    for (it = dataSet.begin(); it!=dataSet.end(); it++)

    {

        if (reversemap.find(it->first) == reversemap.end())

        {

            start = it->first;

            break;

        }

    }

  

    // Если мы не смогли найти отправную точку, то что-то не так с вводом

     if (start.empty())

     {

        cout << "Invalid Input" << endl;

        return;

     }

  

    // Как только у нас есть отправная точка, нам просто нужно идти дальше,

    // следующий из следующего, используя данную хэш-карту

    it = dataSet.find(start);

    while (it != dataSet.end())

    {

        cout << it->first << "->" << it->second << endl;

        it = dataSet.find(it->second);

    }

  
}

  

int main()

{

    map<string, string> dataSet;

    dataSet["Chennai"] = "Banglore";

    dataSet["Bombay"] = "Delhi";

    dataSet["Goa"] = "Chennai";

    dataSet["Delhi"] = "Goa";

  

    printItinerary(dataSet);

  

    return 0;

}
// Реализация C ++ предоставлена Aditya Goel


Выход:

Bombay->Delhi, Delhi->Goa, Goa->Chennai, Chennai->Banglore,

Эта статья составлена Рахулом Джайном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найти маршрут по заданному списку билетов

0.00 (0%) 0 votes