...
- DFS遍历所有节点,对每个节点,先访问其全部的邻接点,再访问节点内容。
- 记录时间戳,从1开始,按DFS遍历的顺序,每个节点的时间戳依次递增,记为
dfn[u]
。 每次访问完一个节点的全部邻接点后,记录从这个节点开始DFS遍历能到的最小时间戳,记为每次访问完一个节点的全部邻接点后,记录从这个节点开始DFS遍历能找到的最小时间戳,记为
low[u]
。提示 dfn[u]
:表示第一次遍历到u的时间戳。low[u]
:表示从点u开始DFS遍历能到达的最小时间戳。- 如果有
dfn[u] == low[u]
,则说明u
是所在强连通分量的最高点,可以把这个强连通分量找出来。
...