Articulation point through non recursive DFS

Question

I wanted to find some way to find if root is an articulation point through non recursive approach. Through recursive approach we can recursively find number of non connected children of root. But I am not finding a way to do that without recursion.

Answer 1

I was able to write one algorithm that I thought might be working. Here it goes:

We have four states of any vertex. UNVISITED, VISITING, VISITED, REVISITING. We keep a dad array and an array that keeps count of unconnected children.

1. We keep on adding vertices to stack starting from root but we dont pop the parent element. For example, we have root 1 connected to 2,3,6,7 then we push 1 to stack but dont pop it. Instead we push other children on top of it. And also we maintain dad for each element. For example, 2,3,6,7 have 1 as their dad.

2. We mark nodes on the stack as VISITING if they were UNVISITED.

3. If during any nodes adjacency list's traversal we find that some element is in VISITING state, we make its state REVISITING but only if this element is not its dad. For eg above all 2, 3 ,6, 7 are in VISITING state. Now if 7's adjacency list is 1, 3, 5, 10, 8, 12 then since 1 is its dad so we dont change state of 1. We go to 3 and see its state as VISITING and also its not 7's dad, we make its state as REVISITING. By now the stack is bottom to top as 1, 2, 3, 6, 7, 5, 10, 8, 12.

4. Now if we come across any element in whose adjacency list there are no UNVISITED elements, if this element's state is VISITING state (not REVISITING) we add 1 to total count of its dad's children (initialized to 0). We ignore adding 1 to its dad's children number if it were in REVISITING state. Also we pop this element out of stack and make its state VISITED.

5. Gradually popping elements we reach root's children (connected or unique). We check by step 4 to calculate number of unique unconnected children of the root. If its greater than 1 then root is an articulation point.

This algorithm seems bit complicated but seems to be working. Any suggestions or questions are welcome.