ML
ну типа любовный треугольник
Size: a a a
2020 April 21
AN
забыл дописать C -> A
тогда да, но модификация решает
AN
Плюс в том, что алгоритм полностью параллельный. Есть некоторое дублирование, но оно скорее всего будет дешевле, чем синхронизация
ML
Ну тогда так, берем все листья, делаем для них то, что я сказал, запоминаем обойденные ноды. Потом берем оставшиеся ноды и делаем с ними то же самое. Если нод много, то можно сэкономить и при следующей итерации не пересчитывать промежуточные ноды, если они уже посчитаны на предыдущей.
Если какие то ноды остались не посещёнными, то это же вроде уже не дерево
AN
Если какие то ноды остались не посещёнными, то это же вроде уже не дерево
А кстати да
AN
И надо еще проверить, что конечная точка у всех одинаковая
ML
кстати, а если у ноды несколько предков, это дерево или уже нет?
ML
вродь цикла нет, под определение подходит
AN
кстати, а если у ноды несколько предков, это дерево или уже нет?
У дерева вроде может быть только один предок
AN
Направленный ациклический граф - там может быть несколько предков, но у дерева, если не ошибаюсь, более сильные ограничения
ML
ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
ML
т.е. всё таки один предок
AN
ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
А, ну тогда гарантированно один предок
ML
отлично. тогда всё просто:
идём от каждого листа к корню:
- если встречаем ноды, которые уже видели на своём пути – мы прошли по циклу – это не дерево
- если оказались в разных корнях – это не дерево
- если встретили ноду с более чем одним предком – это не дерево
- если мы обошли не все ноды – это не дерево
иначе это дерево
идём от каждого листа к корню:
- если встречаем ноды, которые уже видели на своём пути – мы прошли по циклу – это не дерево
- если оказались в разных корнях – это не дерево
- если встретили ноду с более чем одним предком – это не дерево
- если мы обошли не все ноды – это не дерево
иначе это дерево
AN
отлично. тогда всё просто:
идём от каждого листа к корню:
- если встречаем ноды, которые уже видели на своём пути – мы прошли по циклу – это не дерево
- если оказались в разных корнях – это не дерево
- если встретили ноду с более чем одним предком – это не дерево
- если мы обошли не все ноды – это не дерево
иначе это дерево
идём от каждого листа к корню:
- если встречаем ноды, которые уже видели на своём пути – мы прошли по циклу – это не дерево
- если оказались в разных корнях – это не дерево
- если встретили ноду с более чем одним предком – это не дерево
- если мы обошли не все ноды – это не дерево
иначе это дерево
Ага. Дублирование можно уменьшить путем исключения посещенных нод в следующем заходе.
АО
я чёт вот подумал... а для юнити (этот) на KotlinJS пишут?
ML
я чёт вот подумал... а для юнити (этот) на KotlinJS пишут?
там же не совсем js
ML
а какой то их свой script
АО
а, не знал
AL
а, не знал
Ну и судя по всему UnityScript они уже не поддерживают некоторое время.