Хотя я не знаю ни одного существующего алгоритма, который делает это, я могу подумать об одном.
Пусть узел входа будет root , и t узел arget (чтобы найти его доминаторы) будет t .Создайте дерево DFS с корнем в root .
Теперь обратите внимание, что набор доминант t является подмножеством предков t надерево DFS и только передние ребра и поперечные ребра могут «избегать» этих узлов на пути от root до t .Итак:
- Для каждого узла узел , пусть f (узел) будет самым старшим предком t , который может достигать узел не ходя по другим предкам т .Это может быть вычислено в линейном времени с запоминанием.
- Для каждого ребра x → y , где y является предком t , всеузлы, которые являются строгими наследниками f (x) и строгими предками y , не являются доминантами t .(потому что путь root → ... → f (x) → ... → x → y → ... → t не проходит через эти узлы)
Алгоритм ( O (n + m) ) будет выглядеть следующим образом:
- Сделать дерево DFS с корнем root .
- Отметить всепредки t в качестве «возможных кандидатов».
- Вычисление f (узел) для всех узлов.
- Для каждого x → y как описано выше, пометьте список узлов в пути f (x) → ... → y (исключая конечные точки) как «не может быть доминантами» в O (1) время по суммированной таблице. (аналогично таблице суммированных площадей, но в 1D)
- Остальные кандидаты являются доминирующими.
Не уверен, что это проще.