我在读关于在图中找到连接点的算法。
When we are in vertex u and v is its neighbor, then if dfs_low(v) >= dfs_num(u) then u is a cut vertex
dfs_num(i)对dfs中的顶点进行编号。dfs_low(i)告诉除其父顶点外，从i可到达的编号最低的顶点。我想知道这个算法在3节点循环中是如何工作的。（看起来像个三角形）。
运行这个算法，我得到（其中I=0，1，2）
dfs_num(i) = i
dfs_num(i) = 0
这将返回0作为切割顶点，这显然不是一个连接点。
我想我在这里有些误会。有人能澄清一下吗？
最佳答案
根是一种特殊情况，因为它没有父级如果根在DFS树中有多个子节点，则它是一个连接点非根节点v是一个连接点，前提是且仅当它有一个子树，且没有背边指向v的祖先。