在Tarjan的算法上有许多资源可以找到关于单个入口节点的支配树。但是,我只想找到树的单个节点的支配者。
有没有比使用Tarjan的O(m log n)时间算法更简单的方法来计算支配树,然后我们遍历树来查找特定节点的支配者?对于单节点情况,我想比O(m log n)时间更快地完成此操作。
虽然我不知道有任何现有算法可以做到这一点,但我可以想到一个。
让入口节点为根,目标节点(找到其支配者)为t。创建一个以root为根的DFS树。
现在请注意,t的支配者集合是DFS树上t的祖先的子集,并且只有前向边和交叉边可以“避免”从根到t的路径上的那些节点。所以:
算法(O(n + m))将是:
不确定这是否更容易。