b
“есть ли общий потомок у двух вершин”
Size: a a a
2020 September 03
CD
есть ли общий потомок двух вершин в DAG - Е, обходить и только это
b
ну и какая будет сложность?
CD
ну E
b
что E
CD
количество потомков вершины - Е, обходить и только это
CD
что E
число ребер
b
т.е. N
b
можно сделать за logN
CD
можно сделать за logN
нельзя
CD
для дерева можно за 1 :)
CD
hyperloglog - супердостижение, дает примерную оценку числа потомков вершины без обхода
p
“есть ли общий потомок у двух вершин”
Ну это задача поиска одинакового элемента в двух массивах
CD
именно
b
а сорри
b
я дерево представлял
CD
в дереве 1
CD
вершина дерева просто отрезок листьев
CD
хорошие новости в графах начинаются с чего-то вроде "планарность"
b
вершина дерева просто отрезок листьев
да я не про это