利用dfs顺序来确定各个点之间的关系


正文


  我们有一个栈,还有一个low数组和一个dfn数组,其中low数组记录从该节点出发所能到达的dfs序最小的节点的编号(这个点一定会是他的祖先,之后说明原因),dfn数组记录的是该节点的dfs序
  在一个联通块上,选取一点开始dfs,记录dfs序,压该点入栈。遍历从该点出发的边:
    1.若到达点不在栈中,对到达点进行dfs,之后用到达点的low值更新当前节点的low值(如果到达点的low值更小的话)
    2.若到达节点在栈中,用到达节点的dfn值更新当前节点的low值
  为什么这么做呢?1不用解释,2如果一个节点的目标节点在栈中,那么目标节点的一定是它的祖先,因为每个节点至多入栈一次,越靠近栈底的元素越老,肯定是处在栈顶的当前节点的祖先。

  若当前节点的dfn值与low值相同,说明当前节点是一个环中最靠近的祖先的节点,此时连续弹栈,直到当前节点被弹出栈。所弹节点就是一个强连通分量上的全部点。

PS:若图上有块是不连通的,那么需要多次启动dfs过程完成整张图的求强连通分量过程。