tarjans-algorithm

Tarjan's articulation point algorithm on strongly connected graph

I have been studying Tarjan's articulation points finding algorithm and it says that the root node is an articulation point if it has more that 1 child. But if the graph is strongly connected, the root node shouldn't be an articulation point even if it has more than 1 child. Can someone please explain?

Solution

  • If a graph is strongly connected then its root will never have 2 child. Remember , we are talking about DFS tree here. Hence in strongly connected graph , DFS-tree's root will only have one child and thats for sure.Try it urself.