Условие

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

Примеры

Ввод: 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

Ввод: 10 AQHFYP MKFXCLZBT AYKOTYQ QIUKGHWCDC IWCGKHMFM WPLHJL MJVAURUDN QIUKGHWCDC MKFXCLZBT IWCGKHMFM PUTRIPYHNQ UQNGAXNP QIUKGHWCDC WPLHJL UQNGAXNP WPLHJL YURTPJNR QIUKGHWCDC Вывод: AQHFYP 3 AYKOTYQ 2 IWCGKHMFM 1 MJVAURUDN 2 MKFXCLZBT 2 PUTRIPYHNQ 2 QIUKGHWCDC 1 UQNGAXNP 1 WPLHJL 0 YURTPJNR 2

Ввод: 10 BFNRMLH CSZMPFXBZ CSZMPFXBZ IHWBQDJ FMVQTU FUXATQUGIG FUXATQUGIG IRVAVMQKN GNVIZ IQGIGUJZ IHWBQDJ LACXYFQHSQ IQGIGUJZ JMUPNYRQD IRVAVMQKN GNVIZ JMUPNYRQD BFNRMLH Вывод: BFNRMLH 3 CSZMPFXBZ 2 FMVQTU 9 FUXATQUGIG 8 GNVIZ 6 IHWBQDJ 1 IQGIGUJZ 5 IRVAVMQKN 7 JMUPNYRQD 4 LACXYFQHSQ 0

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt()
    val tree = mutableMapOf<String, MutableList<String>>() // Дерево родственных связей
    val parentMap = mutableMapOf<String, String>() // Сопоставление потомок -> родитель
    val heights = mutableMapOf<String, Int>() // Высоты вершин
    val hasParent = mutableSetOf<String>() // Запоминаем всех, у кого есть родитель

    repeat(n - 1) {
        val (child, parent) = reader.readLine().split(" ")
        tree.computeIfAbsent(parent) { mutableListOf() }.add(child)
        parentMap[child] = parent
        hasParent.add(child)
        heights[child] = -1 // Отметка, что высота ещё не вычислена
        heights[parent] = -1
    }

    // Находим родоначальника (того, у кого нет родителя)
    val root = heights.keys.find { it !in hasParent } ?: return
    heights[root] = 0

    // Функция для вычисления высоты элемента через рекурсию с мемоизацией
    fun getHeight(name: String): Int {
        if (heights[name] != -1) return heights[name]!! // Если уже вычислено, просто возвращаем
        val parent = parentMap[name] ?: return 0
        val height = getHeight(parent) + 1
        heights[name] = height
        return height
    }

    // Вычисляем высоты всех узлов
    for (name in heights.keys) {
        getHeight(name)
    }

    // Выводим имена в лексикографическом порядке
    for (name in heights.keys.sorted()) {
        writer.write("$name ${heights[name]}\\n")
    }

    reader.close()
    writer.flush()
    writer.close()
}