[CodeChef FEB14]Graph Challenge解题报告(求半支配点)

题意

给一张有向图,使得从1开始按某种顺序DFS,可以让每个点的标号等于其DFS序号。求每个点的半支配点。

题解

使用Lengauer Tarjan算法,对这一算法的描述和证明见我的上一篇博文:

当然本题只需要求半支配点。
首先按照适当顺序DFS,还原题目描述中所称的DFS生成树。然后直接套算法。
代码如下,思路很简单。要点都写在注释中了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注