Give an order for deleting vertices from a graph such that it doesn't disconnect the graph

Question

This is a question from Algorithm Design by Steven Skiena (for interview prep):

An articulation vertex of a graph G is a vertex whose deletion disconnects G. Let G be a graph with n vertices and m edges. Give a simple O(n + m) that finds a deletion order for the n vertices such that no deletion disconnects the graph.

This is what I thought:

1. Run DFS on the graph and keep updating each node's oldest reachable ancestor (based on which we decide if it's a bridge cut node, parent cute node or root cut node)

2. If we find a leaf node(vertex) or a node which is not an articulation vertex delete it.

3. At the end of DFS, we'd be left with all those nodes in graph which were found to be articulation vertices

The graph will remain connected as the articulation vertices are intact. I've tried it on a couple of graphs and it seems to work but it feels too simple for the book.

Answer 1

in 2 steps:

1. make the graph DAG using any traversal algorithm
2. do topology sort

each step finishes without going beyond O(m+n)

Answer 2

Assuming the graph is connected, then any random node reaches a subgraph whose spanning tree may be deleted in post-order without breaking the connectedness of the graph. Repeat in this manner until the graph is all gone.