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   // Add this header

using namespace std;

int solution(vector &T) {
int N = T.size();
unordered_map graph;

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

queue
> q;  // (city, has_used_ticket)
unordered_set visited; // Declare unordered_set properly

q.push(make_pair(0, false));
visited.insert(0);  // Ensure correct insertion

int max_cities = 0;

while (!q.empty()) {
int city = q.front().first;
bool used_ticket = q.front().second;
q.pop();

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;
}

Неудачные тесты:
Пример теста 1: [0, 9, 0, 2, 6, 8, 0 , 8, 3, 0]
Полученный ответ: 0
Ожидаемый ответ: 4
Пример теста 2: [0, 0, 0, 1, 6, 1, 0, 0]
Полученный ответ: 0
Ожидаемый ответ: 3

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