Задача в примере: найти корень дерева вариантов и вывести его название. Ввод устроен так, что сначала дано число N, затем N названий вещей (по одной на строку), затем N чисел — номера родителей для соответствующих узлов. Число 0 означает, что узел является корнем (у него нет родителя). Нужно вывести название узла, у которого родитель равен 0 (то есть корень дерева).
Пошаговое решение
- Прочитай N.
- Считать массив имен вещей items[0..N-1] (по одной строке на название).
- Считать массив родительских узлов parents[0..N-1] (целые числа).
- Найди первый индекс i, для которого parents[i] == 0. Это корень дерева.
- Выведи имя items[i].
Замечания
- Предполагается, что в вводе ровно один корневой узел (один элемент с parent = 0). Если их несколько, можно выбрать первый встретившийся.
- Если корень не найден (нет 0 в списке), задача не имеет однозначного решения; можно вывести пустую строку или обработать отдельно.
- При чтении имен старайся учитывать возможность пробелов внутри имени; в примере имена состоят из одного слова.
Пример решения на Python
- Ввод рассчитывается так, что каждая строка содержит нужное значение.
- Код ищет индекс корня по условию parent == 0 и выводит соответствующее имя.
Пример кода (Python):
import sys
def main():
data = sys.stdin.read().splitlines()
if not data:
return
N = int(data[0].strip())
names = [data[i+1].rstrip('\n') for i in range(N)]
parents = [int(data[N+1+i].strip()) for i in range(N)]
root = None
for i, p in enumerate(parents):
if p == 0:
root = i
break
if root is not None:
print(names[root])
if name == "main":
main()
Пример решения на C++
- В C++ читаем N, затем значения имен с помощью getline (чтобы поддержать имена с пробелами), затем массив родителей.
- Находим первый индекс с parent == 0 и выводим соответствующее имя.
Пример кода (C++):
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
string tmp;
getline(cin, tmp); // удалить остаток новой строки после N
vector<string> names(N);
for (int i = 0; i < N; ++i) {
getline(cin, names[i]);
// в некоторых текстах бывает лишний '\r' (на Windows)
if (!names[i].empty() && names[i].back() == '\r') names[i].pop_back();
}
vector<int> parents(N);
for (int i = 0; i < N; ++i) {
cin >> parents[i];
}
int root = -1;
for (int i = 0; i < N; ++i) {
if (parents[i] == 0) {
root = i;
break;
}
}
if (root != -1) {
cout << names[root];
}
return 0;
}
Пример проверки на данную задачу
Ввод:
5
Рубашка
Джинсы
Футболка
Кроссовки
Ботинки
1
0
1
2
2
Алгоритм найдет индекс корня там, где parent == 0 → это второй элемент (Джинсы) и выведет: Джинсы.
Если нужно, могу адаптировать решение под другой язык или учесть альтернативный формат входных данных.
