NO..ONE..CARES's blog

Second Best Spanning Tree with only Union-Find Disjoint Set or LCA
By NO..ONE..CARES, history, 8 years ago, In English

For find out second best spanning tree is needed to first build mst tree and for each edge from mst tree flag them then again run kruskal. But how to find second best spanning tree only using union find data structure or lca. I want to know both ways :( Thanks in advance :)

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there yet any answer to that by using only DSU? LCA answers are widely known and appear everywhere, but I have seen nowhere anything using the DSU generated by Kruskal (without path compression of course, since path compression destroys the useful information)...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

check this submission 15317414 DSU only

→ Reply