×

EASY

PREREQUISITES

Disjoint Set Data Structure, Simple Math

PROBLEM

There 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.

• You can construct an edge between two nodes a and b iff cost[a] ≥ 0 AND cost[b] ≥ 0
• The cost of the construction of the edge is equal to cost[a] + cost[b]

Some edges already exist. Hence, some nodes are already connected. You wish to find the minimum cost of connecting the entire graph.

QUICK EXPLANATION

We will be using a Disjoin Set Data Structure that supports the following operations

• init(N), initialize N disjoint sets.
• find(A), get the id of the disjoint set to which A belongs.
• join(A,B), merge the two disjoint sets in which A and B belong respectively.

Union-Find 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 K-1 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 K-1 edges at most.

EXPLANATION

As 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 KC2 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

• The lowest cost vertex, x, is automatically the lowest non-negative cost vertex
• We will consider all the edges from x to other vertices in the order of increasing weights, thus we avoid considering edges to vertices with negative weights
• If we are forced to consider an edge to a vertex with large weight (negative cost vertex originally), then we know that we could not have connected to the connected component of that vertex through any vertex whose weight was positive (otherwise we already would be connected to that component).

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] * (K-1) + sum - cost[x]


Where x is the vertex with the smallest cost.

SETTER'S SOLUTION

Can be found here.

TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

2.3k128183169
accept rate: 14%

 3 My solution involves using DFS to find connected components and minimum costs in a connected component. answered 19 Jul '13, 21:33 4.1k●5●23●64 accept rate: 14% @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 , I add u at the front of the adjacency list of v, and v at the front of the adjacency list of u. (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) damn_me3★
 2 I also used DFS to find the connected components. I think its easier to understand as well as to implement than union-find method. answered 20 Jul '13, 00:52 1.5k●8●21●30 accept rate: 0% 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)
 1 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 4.1k●5●23●64 accept rate: 14%
 1 Hello all, I'm applying this approach.. 1. Use DFS to count number of components and minimum tax of each component. 2. If any component has all planets having negative taxes, then answer is -1 3. Otherwise find global min tax value. 4. Compute result = sum of minimum value of all components + (components-2)*global_min Is my algo right ?? Using this approach,I'm able to get right answers in all test cases I can think of..still getting WA.. answered 23 Aug '13, 01:00 2★samkit 161●2●5●10 accept rate: 0% 1 "If any component has all planets having negative taxes, then answer is -1" What if this is true, but there is only one component? Then, surely, the answer is 0 and not -1. Have you checked this case? (23 Aug '13, 01:08) Apart from this, the steps you said are right. (23 Aug '13, 01:09) thanks bro, for your help..now it got accepted. (23 Aug '13, 02:26) samkit2★
 0 DFS is much easier to handle :) answered 19 Oct '13, 07:12 201●3●9●19 accept rate: 0%
 0 Can anyone please provide a test case where my solution is wrong?? I used DFS..but getting WA... answered 28 Nov '13, 19:20 4★r3gz3n 52●1●2●8 accept rate: 0%
 0 nice editorial but code was a little messy, dfs is easier though! answered 01 Jul, 06:18 11●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×11,590
×2,610
×77
×50
×37
×18

question asked: 19 Jul '13, 19:44

question was seen: 6,322 times

last updated: 01 Jul, 06:18