C++ Найдите максимальное количество городов для посещения ⇐ C++

[Anonymous]

Я отвечал на экзамен по C++ и не смог создать алгоритм, решающий вопросы. Пожалуйста, помогите. Ниже приведен набор вопросов и код решения.
Задание 1
Сеть, состоящая из N городов и N-1. даны соединяющие их дороги. Города помечаются различными целыми числами в диапазоне [0... N-1].
Дороги соединяют города таким образом, что каждая пара отдельных городов соединена либо прямой дорогой, либо прямой дорогой. или по пути, состоящему из прямых дорог. Существует ровно один способ добраться до любого города из любого другого города. Другими словами, города и прямые дороги из дерева.
Например, рассмотрим следующую сеть, состоящую из десяти городов и девяти дорог:
Дорога Сеть
Джек живет в городе номер 0. Он хочет спланировать путешествие и посетить как можно больше городов. Тем не менее, он не хочет посещать какой-либо город более одного раза и может передвигаться только по прямым дорогам. Поездка может закончиться в любом городе.
Есть одна проблема. Для посещения каждого города, отмеченного нечетным номером (1, 3, 5, ...), требуется специальный билет. Билеты уже распроданы, но, к счастью, Джек уже купил один такой билет, поэтому он может посетить не более одного города с нечетным номером.
Джеку интересно, сколько городов (включая стартовый) ) он может посетить.
Напишите функцию:
int solution(vector &T)
что, учитывая непустой массив T, состоящий из N целых чисел, описывающих сеть из N городов и N-1 дорог, возвращает максимальное количество городов, которые Джек может посетить .
Массив T описывает сеть городов следующим образом:

• T[0] = 0;
  если T[P] = Q и P=/0, то есть прямая дорога между городами P и Q.

Примеры:

• < li>Дано T = [0, 9, 0, 2, 6, 8, 0, 8, 3, 0],

Пример дорожной сети 01
функция должна возвращать 4, так как существует путь 0 -> 2 -> 3 -> 8. Город номер 3 — единственный город, для которого требуется билет.

• При T = [0, 0, 0, 1, 6, 1, 0, 0],

Пример дорожной сети 02
функция должна верните 3, так как существует путь 0 -> 6 -> 4. На пути нет городов, для которых требуется билет.
Решение:
Напишите эффективный алгоритм для следующих задач. предположения:

• N — целое число в диапазоне [1, ..., 100 000];
• каждый элемент массива T — целое число в диапазоне [0, ..., N-1];
• Между любыми двумя отдельными городами существует ровно одно (возможно, косвенное) соединение.

Я попробовал следующий код, но мое решение сработало только для несколько тестовых запусков.
Мой код C++:
#include
#include
#include
#include
#include

using namespace std;

int solution(vector &T) {
int N = T.size();
if (N == 1) return 1; // If there's only one city, Jack can visit it.

unordered_map graph;

// Construct adjacency list representation of the tree
for (int i = 1; i < N; ++i) {
graph[T].push_back(i);
graph.push_back(T);
}

queue q; // {city, has_used_ticket}
unordered_set visited;

q.push(make_pair(0, false));
visited.insert(0);

int max_cities = 0;

while (!q.empty()) {
pair current = q.front(); // Extract manually
q.pop();
int city = current.first;
bool used_ticket = current.second;

max_cities++; // Count the visited city

for (int neighbor : graph[city]) {
if (visited.find(neighbor) == visited.end()) { // Not visited yet
bool is_odd = (neighbor % 2 == 1);

if (!is_odd || !used_ticket) { // Can visit if even OR first odd city
q.push(make_pair(neighbor, used_ticket || is_odd));
visited.insert(neighbor);
}
}
}
}

return max_cities; // Ensure the function always returns a value
}


Подробнее здесь: https://stackoverflow.com/questions/793 ... s-to-visit