PROBLEM LINKDIFFICULTYEASY PREREQUISITESDisjoint Set Data Structure, Simple Math PROBLEMThere are N nodes in a graph labeled from 1 to N. Each node has an associated cost with it, given by cost array. You wish to connect this graph by constructing edges between the nodes.
Some edges already exist. Hence, some nodes are already connected. You wish to find the minimum cost of connecting the entire graph. QUICK EXPLANATIONWe will be using a Disjoin Set Data Structure that supports the following operations
UnionFind along with Union by Rank and Path Compression is the asymptotically optical way of maintaining Disjoint Sets. After considering the existing set of edges, we will have some disjoint sets, where there are one or more nodes in each set. Let us assume there are K disjoint sets. We only need to put K1 edges This is easily proven by considering that adding each edge reduces the number of disjoint sets by 1. If it doesn't, then the edge is connecting two nodes that are already connecetd. Thus, we only consider K1 edges at most. EXPLANATIONAs we dwell deeper into discussing the solution to the problem we will encounter a lot of difficulty discussing the ideas if we keep reminding ourselves of ignoring the vertices with negative costs. To be able to handle them in the discussion below (and maybe in your implementation as well), we assume that each negative cost is replaced by a very large positive cost. We will see soon that doing this does not affect the optimal answer. We can consider each disjoint set as an independent vertex and try to build a minimum spanning tree on the graph. The problem is, that for K disjoint sets, there may be as many as ^{K}C_{2} edges. We know that we can solve the problem of finding the minimum spanning tree by greedily considering the edges in increasing order of weights. Here comes to our rescue the definition of the weight of edges in the problem statement. Edge Weight for edge from a to b = cost[a] + cost[b] Let x be the vertex for which cost[x] is smallest. An edge between x and any other vertex will have a lower cost than any other edges in the graph. Also, considering all the edges with one end point on x means we are considering sufficient edges for a connected graph! Note how assuming that all negative cost vertices were actually very large positive cost edges allows us to get around several edge cases
Hence, if the answer could be reached before connecting to any vertex with very large weight, we can print the answer, otherwise, we will print 1. Note that we can avoid the sorting step altogether and consider the minimum cost vertices in each connected component. This way, if we know the sum of costs of the minimum cost vertices in each component, the answer is simply cost[x] * (K1) + sum  cost[x] Where x is the vertex with the smallest cost. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Jul '13, 19:44

My solution involves using DFS to find connected components and minimum costs in a connected component. answered 19 Jul '13, 21:33
@tijoforyou Your code does not handle the case for multiple paths with the same vertex, or is it so? When (1>3); then (3>2); and then (2>1) is given as the paths, your code would store it as 1(>2), 2(>1) and 3(>2) as the final list for DFS. Could you clarify how this does not change the correctness of the solution?
(11 Aug '13, 00:17)
@programme I am using adjacency list representation. When (1>3); then (3>2); and then (2>1) is given as the paths, my code would store it as 1(>2>3), 2(>1>3), 3(>2>1). (For each edge
(11 Aug '13, 11:36)
@tijoforyou I really appreciate your help, I finally figured it out. Thanks again!
(11 Aug '13, 20:15)
@programme We are all here to learn and help each other. Happy to help! :D
(11 Aug '13, 20:48)
@tijoforyou What is the mistake with the following code. My code has exactly the same logic as yours, just the way of implementation differs: http://ideone.com/OOQUBQ
(11 Jul '14, 23:11)

I also used DFS to find the connected components. I think its easier to understand as well as to implement than unionfind method. answered 20 Jul '13, 00:52
could u plz look at http://www.codechef.com/viewsolution/2389555 its giving wa
(20 Jul '13, 02:00)
1
I am giving you a test case. Try to figure it out on your own. 7 4 1 2 2 3 1 3 5 6 3 1 1 2 6 8 4
(20 Jul '13, 14:55)

I was going through a few submissions of this problem. Interestingly, @mugurelionut's solution seems way too clear than the editorial itself!! answered 21 Jul '13, 14:14

Can anyone please provide a test case where my solution is wrong?? I used DFS..but getting WA... answered 28 Nov '13, 19:20

Someone please help me to figure out why my solution gives a WA. Link: http://ideone.com/oM1MVe answered 09 Jan, 16:44

nice editorial but code was a little messy, dfs is easier though! answered 01 Jul, 06:18
