### prodipdatta7's blog

By prodipdatta7, history, 6 years ago,

Given a graph of n nodes and m edges. The number of nodes and edges can have at most 100000. After adding each edge to the graph, you have to calculate the Minimum Spanning Tree of the current graph.

it is not any OJ problem. The problem idea has come to my mind but I can't figure out any solution except brute force. Is it possible to write a solution that will pass within 2s? I will be thankful to u if u share any idea related to the problem solution...

• -4

 » 6 years ago, # |   +6 2 ms? No way.
•  » » 6 years ago, # ^ |   0 sorry for the mistake.statement has been updated
 » 6 years ago, # |   0 Auto comment: topic has been updated by prodipdatta7 (previous revision, new revision, compare).
 » 6 years ago, # |   0 What do you mean calculate the MST? Like finding the sum of the MST edges?
•  » » 6 years ago, # ^ |   0 yup.. sum of the MST edges
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 The edges will be given in such a way that the graph will always be connected
 » 6 years ago, # |   +9 Use Link-cut trees, augmented with the operation of finding the maximum weight edge on any path. When a new edge u - v arrives, if it connects two nodes in different connected components just add the edge. Otherwise, find the maximum weight edge on the u - v path in the tree T containing u, v, compare that edge with u - v and if it has greater weight remove it and add u - v, otherwise, do nothing.