割点与割边

定义

删去图就失去连通

实现思路

Tarjan算法

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