tarjans-algorithm - Tarjan 强连通图上的关节点算法

Question

我一直在研究Tarjan 的关节点查找算法，它说如果根节点有 1 个以上的子节点，它就是一个关节点。但是如果图是强连接的，即使它有超过 1 个子节点，根节点也不应该是关节点。有人可以解释一下吗？

Answer 1

如果一个图是强连接的，那么它的根永远不会有 2 个孩子。请记住，我们在这里谈论的是 DFS 树。因此，在强连通图中，DFS-tree 的根只有一个孩子，这是肯定的。自己试试吧。