Find number of connected components after removing a vertex from a tree

Revision en2, by Dec0Dedd, 2021-08-18 14:47:07

Hey, I have a problem and I cannot think of any faster soltuion than $$$O(nm)$$$.

I'm given a tree with $$$n$$$ vertices and $$$n-1$$$ undirected edges. I'm also given $$$m$$$ queries ($$$m \le 10^5$$$) and each of them is an integer $$$x$$$ ($$$1 \le \lvert x \rvert \le n$$$). If $$$x > 0$$$ then we need to remove vertex $$$x$$$ from a tree and print number of connected components in that tree, otherwise if $$$x < 0$$$ then we need to add vertex $$$x$$$ to that tree (and also print number of connected components). Input data is correct i.e. no vertex will be added before it was removed.

What I thought of, was storing degree of each vertex. Then, if vertex $$$v$$$ was removed then number of connected components increases by $$$deg(v)-1$$$, but this way we also need to decrement by one degrees of vertices with edge with $$$v$$$ which can take $$$O(n)$$$ and that leads to $$$O(nm)$$$. Another idea, was to try to solve the problem using dynamic connectivity, but I'm not sure how to connect that problem to mine.

Thanks in advance!

Tags #problem, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Dec0Dedd 2021-08-18 14:47:07 7
en1 English Dec0Dedd 2021-08-18 14:46:32 1112 Initial revision (published)