Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### _maverick's blog

By _maverick, history, 5 years ago, , I got this question in one of my interviews. Let me state the problem statement clearly,

"You're given an undirected weighted graph consisting of N nodes and E edges and all the weights are unique ( meaning no weights will have duplicates ). Note the graph may also be disconnected ( there could be more than one component in your graph ). The nodes in the graph are labelled starting from 1 to N."

Now you're given an operation that you could perform which is, cut( u , v ) , where u is the label of one node and v is the label of another node and u < v . what this operation returns as result for the given u and v is that it takes the minimum weighted edge adds its value to result and then removes it from graph and then checks whether u and v are disconnected if they are disconnected it stops and returns the result. If the u and v are still connected by some means then it checks for the next minimum weighted edge in the graph and adds its value to the existing result value and removes the edge from the graph and then again check whether u and v are disconnected, if disconnected it stops and returns result. If not then again it continues the same procedure with the next minimum weighted edge in the graph.

So now the question is calculate the sum of all cut(u,v) for all u and v pairs in the graph where u < v . Like if N = 3 and say E = 5, (1,2), (1,3), (2,3) will be the all possible (u,v) pairs where u < v, where u and v are labels of the node. Then final SUM = cut(1,2)+cut(1,3)+cut(2,3). As the answer might be big MOD the value with 1e9+7.

So this is the question I got in my interview and I didn't have enough time to process this question and it seemed pretty hard too. And when I asked for hint, use disjoint set data structures was the reply. I had no clue on how to proceed it further. Can some body provide ideas and different approaches that could be taken to solve this problem.Thanks.  Comments (12)
 » So the idea for solving this is to maintain a disjoint set of all the nodes and process the edges in decreasing order of weight. When we process an edge, we want to know how many pairs of nodes are currently connected by only that edge and those edges with greater edges. This is because for all such pairs, cutting them will require removing the current edge. Initially there are 0 connected pairs, and when you get to a new edge that connects two separate components of size a and b, then the number of connected pairs is increased by a*b. Then, if after processing an edge of weight w we have x connected pairs, the answer is increased by w*x.
•  » » mkirsche can you walk through your procedure over this example, I tried but got stuck in between, say there are 5 Nodes in the graph and edge list is of the form ( node1 , node2 , weight ) which is ( 1,5,3 ) ; ( 2,4,2 ) ; ( 1,2,1 ) ; ( 2,3,5 ) ; ( 1,3,4 ) ?