Найдите палиндромный путь заданной длины K в полном двоичном взвешенном графе

Опубликовано: 21 Сентября, 2022

Для заданного полного ориентированного графа с N вершинами, ребра которого весят «1» или «0», задача состоит в том, чтобы найти путь длины ровно K , который является палиндромом. Выведите « YES », если возможно, а затем путь, в противном случае выведите « NO ».

Пример:

Input: N = 3, K = 4
edges[] =  {{{1, 2}, ‘1’}, {{1, 3}, ‘1’}, {{2, 1}, ‘1’}, {{2, 3}, ‘1’}, {{3, 1}, ‘0’}, {{3, 2}, ‘0’}}
Output: 
YES
2 1  2 1 2
Explanation: 

The path followed is “1111” which is palindrome.

Input: N = 2, K = 6
edges[] = { { 1, 2 }, ‘1’ }, { { 2, 1 }, ‘0’ } 
Output: NO

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

  1. Если К нечетно:
    • В каждом случае существует палиндромный путь, если K нечетно.
    • Его можно построить, выбрав любые два узла и пройдя по ним K раз, например, для K = 5: «00000», «11111», «10101», «01010».
  2. Если К четно:
    • Теперь задачу можно разделить на два случая:
      • Если существуют два узла (i, j) такие, что вес ребра i->j равен весу ребра j->i. Затем ответ можно построить, перебирая их, пока не будет достигнута длина пути K.
      • В противном случае, если существуют три различных узла (i, j, k) такие, что вес ребра i->j равен весу ребра j->k . Затем эти три узла можно поместить в центр пути, например …i->j-> i->j->k ->j->k…, чтобы создать палиндром четной длины.
  3. Выведите ответ в соответствии с приведенным выше наблюдением.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*N)
Вспомогательное пространство: O(N*N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ