Ромбовидное наследование
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
Дана схема классов. Классы пронумерованы с 0; parents[i] — список различных классов, от которых напрямую наследуется класс i. Класс не наследуется сам от себя, а циклов нет. Путь наследования из X в Y — цепочка X, C1, …, Cn, Y, где каждый следующий класс — прямой родитель предыдущего (прямой родитель — путь из двух классов). Схема содержит ромб, если существует пара классов X и Y, между которыми есть хотя бы два разных пути наследования. Верните true, если в схеме есть ромб, иначе false.
Пример: [[1, 2], [3], [3], []] → true (из класса 0 в класс 3 ведут два пути: через 1 и через 2).
Источник: Coding Competitions Archive, codejam/2012/round_1c/diamond_inheritance · © Google LLC · Apache-2.0 · условие переведено и дополнено