Pairing graph Problem

#1


Can anyone help me debug the code?

#2

@mohitsethia
the final answer(in your code) will be cout<<(ans/2); because when every pair will be counted 2 times i.e. (a,b) and (b,a) both are taken, so just divide it by 2.
There is a explanation for this in the hint video also, if you want you can have a look at it.

#3

@mohitsethia
Feel free to ask.
If your doubt is solved now, then please mark this as resolved.

#4

@sanyamsinghalmnnit If there are more than two non-connected components, then? wouldn’t this be taken every time a component is considered,
And why does the code gives segmentation fault when no input is provided? Although it passed all the test cases.

#5

@mohitsethia
that ans/2 has nothing to do with number of connected components.
Look this snippet in your code

     for(int i = 0; i < n; i++){
	int superparent_i = g.get_superparent(i);
	ans += (n - g.sz[superparent_i]);
}

here for every node, you are counting the number of nodes which are not in the same connected component and adding that to answer.
Here when lets suppose you are counting for node=1 then your will take all other nodes which are in different components for eg suppose node=5. Then when you will count for node=5 it will do the same thing again and include node=1 there also.
so in this way we have counted (1,5) and (5,1) as different pairs so we need to ignore half count. thats why ans/2 is done.

1 Like
#6

@mohitsethia
it is giving segmentation fault for no input,because it will try to access graph object with any input which will cause the issue.

I hope your doubt is cleared now, feel free to ask.
If it is clear now, then please mark this doubt as resolved.

#7

Actually what I was doing is if there are three components having nodes 1, 2 and 3 respectively, I don’t know why I was taking 1 and 3, 1 and 2 thrice.
Okay I got this. Thanks, I didn’t realize it earlier :slight_smile:

1 Like