I am trying to solve the following graph problem:
We are given a general unweighted and undirected graph and k (k < |V| ) vertices that are already known beforehand. The vertices are deleted sequentially. After each deletion, how many connected components are there?
I thought of using tarjan's algorithm at each step to check if the current vertex to be deleted is a cut vertex so that when the deletion is performed, we can simply add the number of neighbours to the number of connected components. The complexity of this algorithm is O(V(V+E)).
I was told that there is a O(V+E) algorithm to perform this task. But I cannot figure it out. Research on Google also does not reveal much. Could anyone please advise me?
We can use the fact that the vertices are known beforehand.
Let's solve a "reverse" problem: given a graph and a list vertices that are ADDED to it sequentially, compute the number of connected components in the graph after each addition structure.
The solution is pretty straightforward: we can maintain a disjoint set union structure and add all edges incident to the vertex to the graph (it's easy to keep the number of components in this structure: initially, it is equal to the number of vertices and is decreased by one when a union actually happens).
The original problem is reduced to the "reverse" one in the following way:
Let's add all edges that are not incident to any of the deleted vertices to the disjoint set union.
Now we can reverse the list of deleted vertices and add them one by one as described above.
After that, we need to reverse the resulting list that contains the number of components.
Note: this solution is not actually O(V + E), its O(V + E * alpha(V)), where alpha(x) is the inverse Ackermann's function. It is very close to linear for all practical purposes.