【笔记】割点

Chupeiz · 2018-10-20 16:15:03 · 个人记录

标签：割点 强连通分量

判断割点：在进行DFS时识别割点。令G=(V,E)为一个无向连通图，令T为G的一个以顶点r为根的DFS树。那么我们有：DFS中，e=ab是返祖边（dfn[a]和dfn[b]均已求出），那么要么a是b的祖先， 要么a是b的后代子孙。