Skip to content
Search
K
Main Navigation
首页
模板
题库
更多
在线运行
算法博客
Clist统计
Appearance
Menu
Return to top
On this page
Table of Contents for current page
割点与割边
定义
删去图就失去连通
实现思路
Tarjan算法
按DFS序打上时间戳
数组low,用它来存储不经过其父亲能到达的最小的时间戳(走backedge)
DFS,若顶点
u
存在至少一个顶点
v
,且
v
为
u
的子节点,使得
l
o
w
v
≥
d
f
n
u
,即不能回到祖先,那么
u
点为割点
不适用于判断根节点是否为割点