anirudhmittal21k12k's blog

How to Remove an Index from a Disjoint Union Set Graph and Its Subtrees
By anirudhmittal21k12k, history, 18 months ago, In English

I am not able to find a blog or video which would describe how to delete an index and all its children while doing problem http://www.usaco.org/index.php?page=viewproblem2&cpid=644 . I really wanted a dsu solution. Here my implementation just have to implement delink function correctly please help. Here my submission link https://ide.usaco.guide/NX__5jD-hKhlahQ_iks

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use an approach similar to this Finding bridges

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply