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

Задача состоит в том, чтобы найти название предмета, у которого указан нулевой родитель (то есть корень дерева). Это и есть начальная вещь, с которой Никита начал строить дерево вариантов.

Пошаговое решение

1. Прочитай число N — количество предметов.
2. Прочитай N названий предметов в массив names[1…N].
3. Прочитай N целых чисел parent[1…N] — номера родителей (0 означает отсутствие родителей).
4. Найди индекс i такой, что parent[i] == 0.
5. Выведи names[i]. Это и есть начальная вещь.

Комментарий

• 0 означает отсутствие родителя (корень дерева).
• В условии предполагается, что такой корень один; если бы было несколько, обычно выводят первый найденный по порядку индекс.

Сложность

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

Пример применения к тестам

• Пример 1:

  • N = 5
  • names: Рубашка, Джинсы, Футболка, Кроссовки, Ботинки
  • parents: 1, 0, 1, 2, 2
  • Условие parent[i] == 0 выполняется для i = 2, значит, выводим names[2] = Джинсы.

• Пример 2:

  • N = 7
  • names: Кепка, Чёрная футболка, Белая футболка, Шорты, Кроссовки, Джинсы, Кеды
  • parents: 0, 1, 1, 2, 3, 2, 3
  • Условие parent[i] == 0 выполняется для i = 1, значит, выводим names[1] = Кепка.

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