you can use an approach similar to this Finding bridges

Let each edge have time when it will be closed. It's easy to see that it will happen when one of the nodes it connects gets closed. Let the time when some edge is removed be t. Before t-th removal, the edge was in the graph and later it was not. So we can go from the back when graph has no edges. We will iterate and add all edges with t=N-1, then t=N-2, then t=N-3 and so on. After each addition, we can check if graph is connected by keeping track of number of connected components.