Проблема прохождения перелета в одну сторону

Самый простой способ - использовать хеш-таблицы, но у них не самая лучшая сложность в худшем случае ( O (n ² ) )

Вместо этого:

1. Создайте группу узлов, содержащих (src, dst) O (n)
2. Добавьте узлы в список и отсортируйте по src O (n log n)
3. Для каждый узел (назначение) , найдите в списке соответствующий узел (источник) O (n log n)
4. Найдите начальный узел (например, используя топологическая сортировка или маркировка узлов на шаге 3) O (n)

Итого: O (n log n)

(Для обоих алгоритмов мы предполагаем, что длина строк незначительна, т.е. сравнение - O (1))

Постройте две хэш-таблицы (или попытки), одна из которых имеет ключ src, а другая - dst. Выберите один билет наугад и найдите его dst в хэш-таблице src. Повторяйте этот процесс для всех билетов, пока не дойдете до конца (конечного пункта назначения). Теперь найдите его src в хэш-таблице с ключом dst. Повторяйте этот процесс для результата, пока не достигнете начала.

Построение хэш-таблиц занимает O(n), а построение списка - O(n), так что весь алгоритм - O(n).

EDIT: На самом деле вам нужно построить только одну хэш-таблицу. Допустим, вы построили хэш-таблицу с src-ключом. Выберите один билет наугад и, как и раньше, постройте список, ведущий к конечному пункту назначения. Затем выберите другой случайный билет из тех, которые еще не были добавлены в список. Следуйте за ним до тех пор, пока не дойдете до того билета, с которого начали. Повторяйте этот процесс до тех пор, пока не построите весь список. Это все еще O(n), поскольку в худшем случае вы выбираете билеты в обратном порядке.

Edit: в моем алгоритме имена таблиц поменялись местами.

По сути, это граф зависимостей, где каждый билет представляет узел и src и dst airport представляет собой направленные ссылки, поэтому используйте топологическую сортировку для определения порядка полетов.

РЕДАКТИРОВАТЬ: Хотя, поскольку это авиабилет, и вы знаете, что на самом деле составили маршрут, который вы могли бы физически выполнить, отсортируйте его по дате и времени вылета в UTC.

РЕДАКТИРОВАТЬ2: Предполагая, что каждый аэропорт, на который у вас есть билет, использует трехзначный код, вы можете использовать алгоритм, описанный здесь ( Найти три числа, появившихся только один раз ), чтобы определить два уникальных аэропорта путем xoring всех аэропортов вместе.

РЕДАКТИРОВАТЬ3: Вот немного C ++, чтобы решить эту проблему с помощью метода xor. Общий алгоритм выглядит следующим образом, предполагая уникальное кодирование от аэропорта до целого числа (либо предполагая трехбуквенный код аэропорта, либо кодирующее местоположение аэропорта целым числом с использованием широты и долготы):

Во-первых, XOR всех кодов аэропорта вместе. Это должно быть равно исходному аэропорту-источнику XOR и аэропорту конечного назначения. Поскольку мы знаем, что начальный аэропорт и конечный аэропорт уникальны, это значение не должно быть нулевым. Поскольку оно не равно нулю, в этом значении будет установлен хотя бы один бит. Этот бит соответствует биту, который установлен в одном из аэропортов и не установлен в другом; назовите это битом обозначения.

Затем настройте две корзины, каждая со значением XORed из первого шага.Теперь для каждого билета поместите в сегмент каждый аэропорт в зависимости от того, установлен ли в нем бит указателя или нет, и выполните xor код аэропорта со значением в сегменте. Также отслеживайте для каждой корзины, сколько аэропортов отправления и аэропортов назначения попало в эту корзину.

После обработки всех заявок выберите одну из корзин. Количество исходных аэропортов, отправленных в этот сегмент, должно быть на единицу больше или меньше количества аэропортов назначения, отправленных в этот сегмент. Если количество исходных аэропортов меньше количества конечных аэропортов, это означает, что исходный исходный аэропорт (единственный уникальный исходный аэропорт) был отправлен в другую корзину. Это означает, что значение в текущем сегменте является идентификатором исходного аэропорта! И наоборот, если количество аэропортов назначения меньше количества аэропортов-источников, аэропорт конечного назначения был отправлен в другую корзину, поэтому текущая корзина является идентификатором для аэропорта конечного назначения!

struct ticket
{
    int src;
    int dst;
};

int get_airport_bucket_index(
    int airport_code, 
    int discriminating_bit)
{
    return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}

void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
    int xor_residual= 0;

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        xor_residual^= current_ticket->src;
        xor_residual^= current_ticket->dst;
    }

    // now xor_residual will be equal to the starting airport xor ending airport
    // since starting airport!=ending airport, they have at least one bit that is not in common
    // 

    int discriminating_bit= xor_residual & (-xor_residual);

    assert(discriminating_bit!=0);

    int airport_codes[2]= { xor_residual, xor_residual };
    int src_count[2]= { 0, 0 };
    int dst_count[2]= { 0, 0 };

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);

        airport_codes[src_index]^= current_ticket->src;
        src_count[src_index]+= 1;

        int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
        airport_codes[dst_index]^= current_ticket->dst;
        dst_count[dst_index]+= 1;
    }

    assert((airport_codes[0]^airport_codes[1])==xor_residual);
    assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
    assert(abs(src_count[1]-dst_count[1])==1);
    assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));

    int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; 
    // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!

    assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);

    *out_src= airport_codes[src_index];
    *out_dst= airport_codes[!src_index];

    return;
}

int main()
{
    ticket test0[]= { { 1, 2 } };
    ticket test1[]= { { 1, 2 }, { 2, 3 } };
    ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
    ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
    ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
    ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };

    int initial_src, final_dst;

    find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==3);

    find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
    assert(initial_src==4);
    assert(final_dst==1);

    find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    return 0;
}

Каждый аэропорт является узлом . Каждый билет - это край . Составьте матрицу смежности для представления графа. Это можно сделать как битовое поле для сжатия краев. Отправной точкой будет узел, к которому нет пути (его столбец будет пустым). Как только вы это узнаете, вы просто следуете существующими путями.

В качестве альтернативы вы можете построить структуру, индексируемую по аэропорту. Для каждого билета, который вы ищете, это src и dst . Если ни один из них не найден, вам нужно добавить новые аэропорты в свой список. Когда каждый из них найден, вы устанавливаете указатель выхода из аэропорта отправления на пункт назначения, а указатель прилета пункта назначения - на аэропорт отправления. Когда у вас закончились билеты, вы должны пройти весь список, чтобы определить, у кого нет пути.

Другой способ - иметь список мини-поездок переменной длины, которые вы соединяете вместе, когда встречаетесь с каждым билетом. Каждый раз, когда вы добавляете билет, вы видите, совпадают ли концы любой существующей мини-поездки с src или dest вашего билета. Если нет, то ваш текущий билет становится его собственной мини-поездкой и добавляется в список. Если это так, то новый билет прикрепляется к концу (-ям) существующего (-ых) путешествия (-ов), которому он соответствует, возможно, объединяя две существующие мини-поездки вместе, и в этом случае он сократит список мини-поездок на одну.

Хеш-таблица не будет работать для больших размеров (таких как миллиарды в исходном вопросе); любой, кто работал с ними, знает, что они хороши только для маленьких наборов. Вместо этого можно использовать двоичное дерево поиска, что даст сложность O(n log n).

Самый простой способ - это два прохода: Первый добавляет их все в дерево, индексируя по src. Второй проходит по дереву и собирает узлы в массив.

Можем ли мы сделать лучше? Можем, если очень захотим: мы можем сделать это за один проход. Представим каждый билет как узел в списке "нравится". Изначально каждый узел имеет нулевые значения для указателя next. Для каждого билета укажите в указателе его src и dest. Если произойдет столкновение, это означает, что у нас уже есть соседний билет; соедините узлы и удалите совпадение из индекса. Когда вы закончите, вы сделаете только один проход, у вас будет пустой индекс и связанный список всех билетов по порядку.

Этот метод значительно быстрее: это только один проход, а не два; и хранилище значительно меньше (худший случай: n/2; лучший случай: 1; типичный случай: sqrt(n)), настолько, что вы можете использовать хэш вместо двоичного дерева поиска.

Вставьте два хэша: to_end = src -> des; to_beg = des -> src

Выберите любой аэропорт в качестве начальной точки S.

while(to_end[S] != null)
   S = to_end[S];

Теперь S - ваш конечный пункт назначения. Повторите с другой картой, чтобы найти начальную точку.

Без надлежащей проверки это кажется O(N), при условии, что у вас есть достойная реализация хэш-таблицы.

Резюме: ниже приведен однопроходный алгоритм. (т.е. не просто линейный, а просматривающий каждый билет ровно один раз, что, конечно, является оптимальным количеством посещений одного билета). Я поместил резюме, потому что есть много кажущихся эквивалентными решений, и было бы трудно заметить, почему я добавил еще одно. :)

На самом деле мне задали этот вопрос на интервью. Концепция очень проста: каждый билет - это список синглтонов, в котором концептуально два элемента, src и dst.

Мы индексируем каждый такой список в хэш-таблице, используя его первый и последний элементы в качестве ключей, так что мы можем найти за O(1), начинается ли список или заканчивается на определенном элементе (аэропорту). Для каждого билета, если мы видим, что он начинается там, где заканчивается другой список, просто соединяем эти списки (O(1)). Аналогично, если он заканчивается там, где начинается другой список, присоединяем другой список. Конечно, когда мы соединяем два списка, мы, по сути, уничтожаем два списка и получаем один. (Цепочка из N билетов будет построена после N-1 таких связей).

Необходимо соблюдать инвариант, что ключи hashtable являются в точности первым и последним элементами оставшихся списков.

В общем, O(N).

И да, я ответил на этот вопрос на месте :)

Edit Забыл добавить важный момент. Все упоминают две хэш-таблицы, но одна тоже подходит, потому что инвариант алгоритма включает, что только один список билетов начинается или начинается в любом одном городе (если их два, мы немедленно объединяем списки в этом городе и удаляем этот город из хэш-таблицы). Асимптотически разницы нет, просто так проще.

Edit 2 Также интересно, что по сравнению с решениями, использующими 2 хэш-таблицы с N записями каждая, это решение использует одну хэш-таблицу с максимум N/2 записями (что происходит, если мы видим билеты в порядке, скажем, 1-й, 3-й, 5-й и так далее). Таким образом, кроме того, что это быстрее, это также использует примерно половину памяти.

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

Каждый аэропорт - узел, каждый билет - ребро. Давайте пока сделаем каждое ребро ненаправленным.

На первом этапе вы строите граф: для каждого билета вы ищете источник и пункт назначения и строите ребро между ними.

Теперь, когда граф построен, мы знаем, что он ациклический и что через него проходит единственный путь. В конце концов, у вас есть билеты только на те рейсы, которые вы совершили, и вы никогда не посещали один и тот же аэропорт один раз.

На втором этапе вы выполняете поиск в графе: выбираете любой узел и начинаете поиск в обоих направлениях, пока не обнаружите, что не можете продолжать. Это и есть ваш источник и пункт назначения.

Если вам нужно конкретно указать, что является источником, а что пунктом назначения, добавьте свойство директории к каждому ребру (но сохраните граф ненаправленным). Когда у вас есть кандидаты на источник и пункт назначения, вы можете определить, кто из них кто, на основании ребра, соединенного с ними.

Сложность этого алгоритма будет зависеть от времени, которое требуется для поиска конкретного узла. Если вы можете достичь O(1), то время должно быть линейным. У вас есть n билетов, поэтому вам потребуется O(N) шагов для построения графа, затем O(N) для поиска и O(N) для восстановления пути. Все равно O(N). Матрица смежности даст вам это.

Если вы не можете выделить место, вы можете сделать хэш для узлов, что даст вам O(1) при оптимальном хэшировании и прочей ерунде.

Если вы предполагаете структуру соединяемого списка, которая может хранить все (возможно, на диске):

1. Создайте 2 пустые хэш-таблицы S и D
2. возьмите первый элемент
3. найдите его src в D
4. Если найден, удалите связанный узел из D и свяжите его с текущим узлом
5. Если не найден, вставьте узел в S по ключу src
6. повторите с 3 в другую сторону src<->des, S<->D
7. повторите с 2 со следующим узлом.

O(n) времени. Что касается пространства, парадокс дня рождения (или что-то похожее на него) приведет к тому, что ваш набор данных будет намного меньше, чем полный набор. В случае невезения, когда он все же становится большим (худший случай - O(n)), вы можете удалить случайные пробеги из хэш-таблицы и вставить их в конец очереди обработки. Ваша скорость может упасть, но пока вы можете значительно превысить порог ожидания коллизий (~O(sqrt(n))), вы должны ожидать, что ваш набор данных (таблицы и входная очередь вместе взятые) будет регулярно уменьшаться.

Создайте две структуры данных:

Route
{
  start
  end
  list of flights where flight[n].dest = flight[n+1].src
}

List of Routes

А затем:

foreach (flight in random set)
{
  added to route = false;
  foreach (route in list of routes)
  {
    if (flight.src = route.end)
    {
      if (!added_to_route)
      {
        add flight to end of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
    if (flight.dest = route.start)
    {
      if (!added_to_route)
      {
        add flight to start of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
  }
  if (!added to route)
  {
    create route
  }
}

Давайте на время забудем о структурах данных и графах.

Сначала я должен отметить, что все сделали предположение об отсутствии петель. Если маршрут проходит через один аэропорт дважды, то это гораздо большая проблема.

Но давайте пока оставим это предположение.

Входные данные на самом деле уже являются упорядоченным множеством. Каждый билет является элементом отношения, которое вносит порядок в набор аэропортов. (Английский не является моим родным языком, поэтому это могут быть не совсем корректные математические термины)

Каждый билет содержит информацию следующего вида: airportX < airportY, поэтому при одном проходе по билетам алгоритм может воссоздать упорядоченный список, начиная с любого аэропорта.

Теперь отбросим "линейное предположение". Из такого материала нельзя определить никакого отношения порядка. Входные данные должны рассматриваться как правила производства для формальной грамматики, где словарный запас грамматики - это набор названий аэропортов. Такой билет:

src: A
dst: B

фактически является парой производств:

A->AB
B->AB

из которых вы можете оставить только одно.

Теперь вы должны сгенерировать все возможные предложения, но вы можете использовать каждое производящее правило один раз. Самое длинное предложение, в котором каждое производящее правило используется только один раз, является правильным решением.

Обратите внимание, что если бы задача была только для определения аэропортов отправления и назначения (вместо восстановления всей поездки), головоломка, вероятно, стала бы более интересной.

А именно, предполагая, что коды аэропортов заданы как целые числа, аэропорты источника и назначения могут быть определены с использованием O (1) проходов данных и O (1) дополнительной памяти (т. Е. Без использования хэш-таблиц, сортировки, двоичного поиска, и тому подобное).

Конечно, как только вы найдете источник, индексирование и прохождение всего маршрута также становится тривиальным делом, но с этого момента для всего этого в любом случае потребуется как минимум O (n) дополнительной памяти (если вы не можете отсортировать данные на месте, что, кстати, позволяет решить исходную задачу за O (n log n) времени с O (1) дополнительной памятью)

Предварительные условия

Прежде всего, создайте какую-нибудь структуру подтрипа, которая содержит часть вашего маршрута.

Например, если ваш полный маршрут имеет вид a-b-c-d-e-f-g, то подтрипом может быть b-c-d, т.е. связный подпуть вашего маршрута.

Теперь создайте две хэш-таблицы, которые сопоставляют город со структурой подтрипа, в которую входит город. Таким образом, одна хэш-таблица обозначает город, с которого начинается подтрип, а другая - города, которыми заканчивается подтрип. Это означает, что один город может встречаться не более одного раза в одной из хэш-таблиц.

Как мы увидим позже, хранить нужно не все города, а только начало и конец каждого подтрипа.

Построение подтрипов

Теперь возьмем билеты один за другим. Предположим, что билет следует из x в y (представлен (x,y)). Проверьте, является ли x концом некоторого подтрипа s (поскольку каждый город посещается только один раз, он не может быть концом другого подтрипа). Если x является началом, просто добавьте текущий билет (x,y) в конец подтрипа s. Если нет подтрипа, заканчивающегося на x, проверьте, есть ли подтрип t, начинающийся на y. Если да, то добавьте (x,y) в начало t. Если такого подтрипа t также не существует, создайте новый подтрип, содержащий только (x,y).

Работа с подтрипами должна осуществляться с использованием некоторых специальных "трюков".

• Создание нового подтрипа s, содержащего (x,y), должно добавить x в хэш-таблицу для "городов начала подтрипа" и добавить y в хэш-таблицу для "городов окончания подтрипа".
• Добавление нового билета (x,y) в начало подтрипа s=(y,...), должно удалить y из хэш-таблицы начальных городов и вместо этого добавить x в хэш-таблицу начальных городов.
• Добавление нового билета (x,y) в конец подтрипа s=(...,x), должно удалить x из хэш-таблицы конечных городов и вместо этого добавить y в хэш-таблицу конечных городов.

С такой структурой подтрипы, соответствующие городу, могут быть выполнены за амортизированное O(1).

После того, как это сделано для всех билетов, у нас есть несколько подтрипов. Заметим, что после этой процедуры мы имеем не более (n-1)/2 = O(n) таких подтрипов.

Конкатенация подтрипов

Теперь мы просто рассматриваем подтрипы один за другим. Если у нас есть подтрип s=(x,...,y), мы просто смотрим в нашей хэш-таблице конечных городов, есть ли подтрип t=(...,x), заканчивающийся на x. Если да, то конкатенируем t и s в новый подтрип. Если нет, то мы знаем, что s - наш первый подтрип; тогда смотрим, есть ли другой подтрип u=(y,...), начинающийся с y. Если да, то конкатенируем s и u. Мы делаем это до тех пор, пока не останется только один подтрип (этот подтрип и есть весь наш исходный путь).

Надеюсь, я не упустил что-то из виду, но этот алгоритм должен работать за:

• построение всех подтрипов (максимум O(n)) может быть выполнено за O(n), если мы реализуем добавление билетов в подтрип за O(1). Это не должно быть проблемой, если у нас есть какая-то хорошая структура указателей или что-то подобное (реализация подтрипов в виде связанных списков). Также изменение двух значений в хэштейбле является (амортизированным) O(1). Таким образом, этот этап занимает O(n) времени.
• конкатенация подтрипов, пока не останется только один, также может быть выполнена за O(n). Чтобы убедиться в этом, нам просто нужно посмотреть, что делается на втором этапе: поиск в хэш-таблице, который требует амортизации O(1) и конкатенация подтрипов, которая может быть выполнена за O(1) с помощью конкатенации указателей или чего-то подобного.

Таким образом, весь алгоритм занимает время O(n), которое может быть оптимальным O-граничным, поскольку по крайней мере каждый билет может быть просмотрен.

Никаких хешей или чего-то подобного. Настоящий размер входных данных здесь не обязательно является количеством билетов (скажем, n ), но общим «размером» (скажем, N ) билетов, общим количеством char необходим для их кодирования.

Если у нас есть алфавит из k символов (здесь k примерно 42), мы можем использовать методы сегментной сортировки для сортировки массива из n строк общий размер N , которые закодированы алфавитом из k символов за O (n + N + k) раз. Следующее работает, если n <= N (тривиально) и k <= N (ну N - миллиарды, не так ли)

1. В закажите билеты, извлеките все коды аэропортов из билетов и сохраните их в структуре , которая имеет код в виде строки и индекс билета в виде числа.
2. Сортировка этого массива структур структур в соответствии с их кодом
3. Выполните этот отсортированный массив и присвойте порядковый номер (начиная с 0 ) каждому вновь встреченному коду авиакомпании. Для всех элементов с одинаковым кодом (они идут подряд) перейдите в тикет (мы сохранили номер с кодом) и измените код (выберите правый, src или dst ) ) билета на порядковый номер.
4. Во время этого прогона по массиву мы можем идентифицировать исходный источник src0 .
5. Теперь все билеты имеют src и dst , переписанные как порядковые номера, и билеты можно интерпретировать как один список, начинающийся с src0 .
6. Составьте список (= топлогическая сортировка с отслеживанием расстояния от src0 ) в билетах.

Это простой случай матрицы конечного автомата с одним путём. Извините за псевдокод в стиле C #, но было проще выразить идею с помощью объектов.

Во-первых, постройте матрицу магистрали. Прочтите мое описание того, что такое матрица магистрали (не беспокойтесь об ответе конечного автомата, просто объясните матрицу магистрали) на . Каковы некоторые стратегии для тестирования больших конечных автоматов? .

Однако описанные вами ограничения делают случай простым конечным автоматом с одним путем. Это простейший конечный автомат с полным покрытием.

Для простого случая с 5 аэропортами
вершины узлов = src / точки входа,
узлы горизонта = dst / точки выхода.

   A1 A2 A3 A4 A5
A1        x
A2  x
A3           x
A4              x
A5     x

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

Чтобы получить путь к машине, вы должны отсортировать матрицу в

   A1 A2 A3 A4 A5
A2  x
A1        x
A3           x
A4              x
A5     x

Или сортировать в диагональную квадратную матрицу - собственный вектор упорядоченных пар.

   A1 A2 A3 A4 A5
A2  x
A5     x
A1        x
A3           x
A4              x

где упорядоченные пары - это список билетов:

a2: a1, a5: a2, a1: a3, a3: a4, a4: a5.

или в более формальных обозначениях,

<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.

Хммм .. упорядоченные пары, да? Чувствуете намек на рекурсию в Лиспе?

<a2,<a1,<a3,<a4,a5>>>>

Есть два режима машины,

1. планирование поездки - вы не знаете, как там много аэропортов, а ты нужен общий план поездки для неуказанное количество аэропортов
2. реконструкция рейса - у вас есть все билеты на магистраль прошлой поездки но все они - одна большая стопка в свой перчаточный ящик / багажную сумку.

Полагаю, ваш вопрос касается реконструкции поездки. Итак, вы случайным образом выбираете один билет за другим из этой стопки билетов.

Мы предполагаем, что стопка билетов неопределенного размера.

     tak mnx cda 
bom    0
daj       0
phi           0

Где значение 0 означает неупорядоченные билеты. Давайте определим неупорядоченный билет как билет, где его dst не совпадает с src другого билета.

Следующий запрос обнаруживает совпадение mnx (dst) = kul (src).

     tak mnx cda kul
bom    0
daj       1
phi           0
mnx               0

В любой момент, когда вы выбираете следующий билет, есть вероятность, что он соединит два последовательных аэропорта. Если это произойдет, вы создаете узел кластера из этих двух узлов:

<bom,tak>, <daj,<mnx,kul>>

и матрица сокращается,

     tak cda kul
bom    0
daj          L1
phi       0

где

L1 = <daj,<mnx,kul>>

- подсписок основного списка.

Продолжайте выбирать следующие случайные билеты.

     tak cda kul svn xml phi
bom    0
daj          L1
phi       0
olm               0
jdk                   0
klm                       0

Сопоставьте existent.dst с new.src
или existent.src в new.dst:

     tak cda kul svn xml
bom    0
daj          L1
olm               0
jdk                   0
klm      L2


<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>

Вышеупомянутое топологическое упражнение предназначено только для визуального восприятия. Ниже приводится алгоритмическое решение.

Идея состоит в том, чтобы сгруппировать упорядоченные пары в подсписки, чтобы снизить нагрузку на хэш-структуры, которые мы будем использовать для размещения билетов. Постепенно будет появляться все больше и больше псевдобилетов (сформированных из объединенных совпавших билетов), каждый из которых будет содержать растущий подсписок упорядоченных пунктов назначения. Наконец, останется один псевдобилет, содержащий полный вектор маршрута в его подсписке.

Как видите, возможно, лучше всего это сделать с помощью Lisp.

Однако, в качестве упражнения со связанными списками и картами ...

Создайте следующие структуры:

class Ticket:MapEntry<src, Vector<dst> >{
  src, dst
  Vector<dst> dstVec; // sublist of mergers

  //constructor
  Ticket(src,dst){
    this.src=src;
    this.dst=dst;
    this.dstVec.append(dst);
  }
}

class TicketHash<x>{
  x -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.x, t);
  }
}

Так что эффективно,

TicketHash<src>{
  src -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.src, t);
  }
}

TicketHash<dst>{
  dst -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.dst, t);
  }
}    

TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src

Когда билет случайно выбран из стопки,

void pickTicket(Ticket t){
  // does t.dst exist in mapbyDst?
  // i.e. attempt to match src of next ticket to dst of an existent ticket.
  Ticket zt = dstExists(t);

  // check if the merged ticket also matches the other end.
  if(zt!=null)
    t = zt;

  // attempt to match dst of next ticket to src of an existent ticket.
  if (srcExists(t)!=null) return;

  // otherwise if unmatched either way, add the new ticket
  else {
    // Add t.dst to list of existing dst
    mapbyDst.add(t); 
    mapbySrc.add(t);
  }
}

Проверить наличие dst:

Ticket dstExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbyDst.getEntry(t.src);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbySrc.getEntry(t.src);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbyDst.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbyDst.add(zt);

  return zt;
}

Ticket srcExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbyDst.getEntry(t.dst);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbySrc.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbySrc.add(zt);

  return zt;
}

Проверить наличие существующего src:

Ticket srcExists(Ticket t){
  // find existing ticket whose src matches t.dst
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt == null) return null;

  // if an ordered pair is matched

  // remove the dst from mapbyDst
  mapbySrc.remove(zt);

  //Merge new ticket into existent ticket
  //reinsert existent ticket and discard new ticket.
  mapbySrc.getEntry(zt);

  //append sublist of new ticket to sublist of existent ticket
  zt.srcVec.append(t.srcVec);
  return zt;
}

Мне кажется, что в приведенном выше есть несколько опечаток, но концепция должна быть правильной. Любая обнаруженная опечатка, кто-нибудь может помочь исправить ее, пожалуйста.