I have a graph with N nodes and M edges. It is a single component.
Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such components is required for each deleted node. Note that only a single node is deleted at any point of time.
I need to do this for all the nodes of the graph in a linear time.
Is this possible in linear time? I am able to do this in O(n^2) by running dfs for each node.