版本比较

标识

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

...

  1. DFS遍历所有节点,对每个节点,先访问其全部的邻接点,再访问节点内容。
  2. 记录时间戳,从1开始,按DFS遍历的顺序,每个节点的时间戳依次递增,记为dfn[u]
  3. 每次访问完一个节点的全部邻接点后,记录从这个节点开始DFS遍历能到的最小时间戳,记为每次访问完一个节点的全部邻接点后,记录从这个节点开始DFS遍历能找到的最小时间戳,记为low[u]

    提示

    dfn[u]:表示第一次遍历到u的时间戳。

    low[u]:表示从点u开始DFS遍历能到达的最小时间戳。

  4. 如果有dfn[u] == low[u],则说明u是所在强连通分量的最高点,可以把这个强连通分量找出来。

...