I am getting WA and I have even considered the case where all planets are connected to each other and the answer is zero for that. please help me. here the the link to my code.

consider dis input

8 5,

2 3,

4 5,

6 7,

7 8,

8 2,

1,

-1,

2,

3,

-1,

4,

1,

3

ur program is giving wrong ans

disjoint -= 2;

ans += disjoint * min_all;

This code is wrong. Suppose we have 4 connected components.

Let m1, m2, m3, & m4 be the minimum of each connected component sorted in increasing order.

Then

if m1 < 0 ans is -1;

otherwise the answer is 3 * min1 + Sum(m2, m3, m4); The general formula is (n - 1) m1 + sum(mi)

n here represents the number of connected components.

@a9393j007: the bug in your code is that u have not marked the adjacency vice versa:

```
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v); //v is also adjacent to W, it is the fix.
}
```

this is your modified submission which get AC.

http://www.codechef.com/viewsolution/2384136

Well some faults that i could find was that when you are creating an edge you are not making it bi-directionalâ€¦ i.e when you use addEdge function call it for both (a,b) and (b,a)â€¦Otherwise for a test case in which connections(agreements) are like

1 2

3 2

4 1

your code will identify(incorrectly) 3 disjoint componentsâ€¦while all of 1 2 3 4 are connected.

Secondly, when input for costs are all negative you seem to give 0 as the answer even if there are no connections!

This is because you break your DFS loops as soon as you get negative value of cost for all vertices of a single connected component.Thus for correcting that u must continue the DFS loops to get exact number of connected components then check for complete connectedness.

@a9393j007 pleaseâ€¦explain meâ€¦for the input 8 5,2 3,4 5,6 7,7 8,8 2,1,-1,2,3,-1,4,1,3

the connected planets are

1 (1)

2,3,6,7,8 (1)for 7

and 4,5 (3) for 4

the correct answer should be 6 and not 5

bcz cost of connecting planet 1 and 7 is = 1+1=2

and cost of connecting planet 1 and 4 is = 1+3 =4

so total cost = 2+4 = 6

my solution is giving right ans for all the above test cases bt Wrong Answer on submissionâ€¦Here is the link to my solutionâ€¦ http://www.codechef.com/viewsolution/5478497 â€¦plz helpâ€¦

The answer should be zero since all the planets are connected and there is only one connected component. Your code gives 9 while the right answer is 0

@a9393j007 try as many possibility as u can using pen and paper and later check if your program produces correct outputâ€¦

This is one of the test case i used to test my program before submitting.

in my code,

- i first visit the set of planets which are connected to each other and find there min(min is always positive) and then add it to answer.
- so if we have 4 components so i have already added m1,m2,m3,m4 to answer in the DFS().
- at the end 2 components are already connected so i use disjoint-=2 and add disjoint*min_all to answer.

actually in your test case all the planets are not connected and yaaa my code is giving wrong answer for you test case. answer should be 5 not 9 .

Can you explain the logic u used to solve this problem?

i have already explained the logic.

I believe ravishanker is right about that.

thnx for clarifying

It is quite strange that even for that modified AC code the case

5 0,-1,-1,-1,-1,-1 will give 0 while actual answer is -1â€¦i donâ€™t think there was any constraint disallowing all negative costs or 0 connections.

If the number of connected components is 1 then you can reach any planet from any other planet thus there is no need to pay anything thatâ€™s y the answer should be 0 even if all the costs are -ve

ya I got it now â€¦ thx for that.

If there are no connections how are number of connected components 1??

They should be N.