Алгоритм генеалогического древа

I ' Я работаю над составлением набора задач для вводного курса компьютерной грамотности и пришел к вопросу, который на первый взгляд кажется очень простым:

Вам дается список людей с именами их родителей, их рождением даты и даты их смерти. Вам интересно узнать, кто в какой-то момент своей жизни был родителем, бабушкой или дедушкой, прадедушкой и т. Д. Разработайте алгоритм, чтобы пометить каждого человека этой информацией как целое число (0 означает, что у человека никогда не было child, 1 означает, что человек был родителем, 2 означает, что этот человек был дедушкой или бабушкой и т. д.)

Для простоты вы можете предположить, что семейный граф представляет собой DAG, чья неориентированная версия является деревом.

Интересная проблема здесь в том, что вы не можете просто посмотреть на форму дерева, чтобы определить эту информацию. Например, у меня 8 прапрабабушек и дедушек, но поскольку ни один из них не был жив, когда я родился, при жизни никто из них не был прапрапрадедушкой.

Лучший алгоритм, который я могу придумать для этой задачи, выполняется за время O (n ² ), где n - количество человек. Идея проста - начать DFS от каждого человека, найти самого дальнего потомка в генеалогическом древе, который родился до даты смерти этого человека. Однако я почти уверен, что это не оптимальное решение проблемы. Например, если в графе всего два родителя и их n детей, то проблема может быть решена тривиально за O (n). Что я' m надеется на какой-то алгоритм, который либо превосходит O (n ² ), либо время выполнения которого параметризовано по форме графа, что делает его быстрым для широких графов с постепенной деградацией до O (n ² ) в худшем случае.