Fork me on GitHub

有关dfn-low

本文开始啦感谢您的阅读

仅仅是写一下割边,割点,强连通分量,以及双连通分量的代码思路

割点:

割点需满足的条件:

  1. 若该点是跟根节点,那么需要有至少两个不连通的儿子
  2. 如果该节点不是根节点,那么至少有一个子节点无法到达该点的祖先节点

割边:

  1. 筛掉父亲边
  2. 是否是树边

强连通分量:

  1. 运用栈
  2. 当dfn=low时,栈顶到当前位置为一个强连通分量

双联通分量:
未完待续……