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

Давайте разберем поставленную задачу шаг за шагом.

Задача

Вам даны N предметов одежды, и для каждого из них указан родитель (то есть, от чего или кого он зависит в иерархии). Ваша задача — определить наименование вещи, с которой Никита начал строить дерево вариантов, т.е. найти корень дерева.

Решение

1. Понимание структуры задачи:

   • У нас есть N предметов одежды, каждый из которых имеет номер (0, 1, 2 ... N-1).
   • У каждой вещи есть родительская вершина (номер) или значение 0, указывающее, что это корень дерева.

2. Анализ входных данных:

   • Первая строка — число N (количество предметов).
   • Следующие N строк — названия предметов одежды.
   • Последующие N строк — номера родительских вершин для каждого предмета.

3. Поиск корня:

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

Пример

Для первого примера:

• Ввод:

  5
  Рубашка
  Джинсы
  Футболка
  Кроссовки
  Ботинки
  1
  0
  1
  2
  2
  

1. Список названий:

   • 0: Рубашка
   • 1: Джинсы
   • 2: Футболка
   • 3: Кроссовки
   • 4: Ботинки

2. Список родительских вершин:

   • 0: 1
   • 1: 0 (это корень)
   • 2: 1
   • 3: 2
   • 4: 2

3. Поиск:

   • Ищем номер, который равен 0: он находится на индексе 1.

4. Вывод:

   • Корень: Джинсы.

Для второго примера:

• Ввод:

  7
  Кепка
  Чёрная футболка
  Белая футболка
  Шорты
  Кроссовки
  Джинсы
  Кеды
  0
  1
  1
  2
  3
  2
  3
  

1. Список названий:

   • 0: Кепка
   • 1: Чёрная футболка
   • 2: Белая футболка
   • 3: Шорты
   • 4: Кроссовки
   • 5: Джинсы
   • 6: Кеды

2. Список родительских вершин:

   • 0: 0 (это корень)
   • 1: 1
   • 2: 1
   • 3: 2
   • 4: 3
   • 5: 2
   • 6: 3

3. Поиск:

   • Находим тот предмет, у которого родитель 0: индекс 0.

4. Вывод:

   • Корень: Кепка.

Итог

Таким образом, алгоритм позволяет вам эффективно находить корень дерева вариантов одежды для Никиты. Главное — сосредоточиться на идентификации родительских вершин и находить тот элемент, у которого родитель равен 0.