§06 图结构

割点检测

Tarjan 的姊妹应用：low[child] ≥ dfn[u] 判定割点——删除后图断开的关节点。

割点检测

第 01 / 13 步

割点检测：删除某顶点使连通分量增加，则它是割点。DFS 中用 low 值判定。比较 0 · 交换 0

伪代码


				
					
					1
					procedure cutCheck(u):
				
			
				
					
					2
					  root: childCount >= 2 => cut vertex
				
			
				
					
					3
					  non-root: exists child v with low[v] >= dfn[u] => cut vertex

01 / 13

速度