Skip to content

割点与割边

定义

删去图就失去连通

实现思路

Tarjan算法

  • 按DFS序打上时间戳
  • 数组low,用它来存储不经过其父亲能到达的最小的时间戳(走backedge)
  • DFS,若顶点 u存在至少一个顶点 v ,且vu的子节点,使得 lowvdfnu ,即不能回到祖先,那么 u 点为割点
  • 不适用于判断根节点是否为割点

网站基于vitepress主题open17💙