Гардероб Никиты Никита сохраняет в памяти компьютера графы с комплектами одежды. Каждый граф содержит N предметов. Каждая вещь записана в таблицу и пронумерована. Кроме того,…

Ниже детальное решение задачи и применимость к примерам.

Что нужно сделать

• Найти предмет, у которого значение родителя равно 0. Именно этот предмет является тем, с которого Никита начал строить дерево вариантов.
• Если таких предметов несколько, выбираем первый встречающийся в порядке ввода (обычно в тестах их может быть один).

Пошаговый алгоритм

1. Прочитать N — количество предметов.
2. Прочитать список имен предметов A[1..N].
3. Прочитать список родительских индексов P[1..N].
4. Найти первый индекс i, для которого P[i] = 0.
5. Вывести A[i].

Сложность

• Время: O(N) — нужно пройти по спискам один раз.
• Память: O(N) для хранения имен и чисел.

Применение к примерам из условия

• Пример 1:

  • Имена: Рубашка, Джинсы, Футболка, Кроссовки, Ботинки
  • Родители: 1, 0, 1, 2, 2
  • Первый элемент с P[i] = 0 — это второй предмет: Джинсы.
  • Вывод: Джинсы

• Пример 2:

  • Имена: Кепка, Чёрная футболка, Белая футболка, Шорты, Кроссовки, Джинсы, Кеды
  • Родители: 0, 1, 1, 2, 3, 2, 3
  • Первый элемент с P[i] = 0 — это первый предмет: Кепка.
  • Вывод: Кепка

Дополнительная заметка

• Если в списке окажется более одного элемента с P[i] = 0, расширение задачи обычно предполагает выбрать первый по порядку ввода. Если же задача явно требует другой подход (например, все корни или конкретный корень), нужно уточнить условия.

Если хочешь, могу привести простой пример кода на Python, реализующий этот алгоритм.