Найдите, если возможно, посетить все узлы в данном графе ровно один раз на основе заданных условий.

Учитывая граф, имеющий N+1 узлов с 2*N-1 ребрами и логический массив arr[ ] , задача состоит в том, чтобы найти, можно ли посетить все узлы ровно один раз и вывести любой возможный путь. Также известно, что N-1 ребер идут i-м в (i+1)-й узел, а остальные ребра идут i-м в (n+1)-й узел, если arr[i] равен 0 , иначе (n+1) с -го по i-й .

Примеры:

Input: N = 3, arr = {0, 1, 0}
Output: [1, 2, 3, 4]
Explanation:
from the given data, the edges will:
1 -> 2
2 -> 3
1 -> 4
4 -> 2
3 -> 4

Therefore, one can follow the path: 1 -> 2 -> 3 -> 4

Input: N = 4, arr = {0, 1, 1, 1}
Output: [1, 4, 2, 3]

Подход: Эту проблему можно решить с помощью жадного подхода с некоторыми наблюдениями. Наблюдения приведены ниже:

• Если arr[1] равно 1 , то следуйте по пути [N+1 -> 1 -> 2……..-> N] .
• Если arr[N] равно 0 , то следуйте по пути [1 -> 2 ->……….-> N -> N+1] .
• Если arr[1] равно 0, а arr[N] равно 1 , должно существовать целое число i (1 ≤ i< N) , где arr[i] =0 и arr[i+1] = 1 , тогда путь [1 -> 2 -> ⋯ -> i -> N+1 -> i+1 -> i+2 -> ⋯N] .
• Предыдущий шаг доказывает, что в этом графе всегда существует гамильтонов путь.

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

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