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...
2 ms? No way.
sorry for the mistake.statement has been updated
Auto comment: topic has been updated by prodipdatta7 (previous revision, new revision, compare).
What do you mean calculate the MST? Like finding the sum of the MST edges?
yup.. sum of the MST edges
The edges will be given in such a way that the graph will always be connected
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.