logoChat01.ai

Родословная: подсчет уровней В генеалогическом дре...

Erstellt am: 26. September 2025

Beantwortet mit GPT-5 Thinking von Chat01

Frage

Родословная: подсчет уровней
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.

Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.

Вам дано генеалогическое древо, определите высоту всех его элементов.

Входные данные
Программа получает на вход число элементов в генеалогическом древе 𝑁. Далее следует 𝑁−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

Выходные данные
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

Примечание
Эта задача имеет решение сложности 𝑂(𝑛), но вам достаточно написать решение сложности 𝑂(𝑛2) (не считая сложности обращения к элементам словаря).

Пример ниже соответствует приведенному древу рода Романовых.

Примеры
входные данные
9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
выходные данные
Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2
simple code c++

Gedanke

Providing C++ Solution

The user seems to be asking for simple C++ code for solving a genealogy tree problem. I’ll need to write code that reads the number of people, followed by the family relations. The algorithm will map parent-child relationships and identify the root by finding a person who never appears as a child. Let's accommodate this and return a solution.

Clarifying Input Detail and Root Identification

The input consists of names that include both child and parent relationships, with one root that’s never a child. To find the root, I’ll collect all names and identify those who do not appear as children. The root is the one name that only appears as a parent. Then, we can compute tree heights using DFS, BFS, or recursion.

Optimizing with BFS

Okay, they allow O(n^2), but I’ll implement O(n log n) using BFS. The plan is to create a graph of children, then use BFS to calculate depths from the root. After that, I'll sort and print the names in lexicographic order along with their heights. I’ll ensure no extra spaces or issues with underscores.

Writing the Code

I will first read the integer N, then loop through pairs of child and parent to build a mapping (parent_map) and an adjacency list (children). Then, I’ll find the root by identifying the name not present in the child set. After that, I’ll use BFS to compute the depths of each node and print them sorted by name. If some nodes have no children, they'll be handled by ensuring the adjacency list defaults to empty. I'll make sure no names are skipped in the depth calculation.

Thought for 41s

Antwort

Вот простой и понятный вариант на C++: читаем пары «потомок родитель», находим родоначальника (тот, кто ни разу не встречается как потомок), делаем обход в ширину от него и получаем высоты. Затем выводим всех по лексикографическому порядку.

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;

    unordered_map<string, vector<string>> children; // parent -> list of children
    unordered_set<string> all_names, child_names;

    for (int i = 0; i < N - 1; ++i) {
        string child, parent;
        cin >> child >> parent;
        children[parent].push_back(child);
        all_names.insert(child);
        all_names.insert(parent);
        child_names.insert(child);
    }

    // Найти родоначальника: это тот, кто не встречается среди потомков
    string root;
    for (const auto& name : all_names) {
        if (!child_names.count(name)) {
            root = name;
            break;
        }
    }

    // BFS для вычисления высот
    unordered_map<string, int> height;
    queue<string> q;
    height[root] = 0;
    q.push(root);

    while (!q.empty()) {
        string cur = q.front(); q.pop();
        int h = height[cur];
        auto it = children.find(cur);
        if (it != children.end()) {
            for (const string& ch : it->second) {
                height[ch] = h + 1;
                q.push(ch);
            }
        }
    }

    // Список имён в лексикографическом порядке и вывод высот
    vector<string> names(all_names.begin(), all_names.end());
    sort(names.begin(), names.end());
    for (const string& name : names) {
        cout << name << ' ' << height[name] << '\n';
    }
    return 0;
}

Подходит под ограничения задачи и даёт именно тот формат вывода, что в примере.

Diesen Q&A teilen