Graph - Pairing

not able to pass all the test cases

Hi Koshima

Please check your logic for this input :
1000 1
1 2

Your code’s output is: 2

But if you see according to the question we have to find the number of ways in which cities can be chosen and there is an undirected road between the two cities X and Y. So, for this particular example

if there is no path between any two cities then it should be (1000 * 999 i.e. no path for all the 1000 cities to reach other 999 cities and as the paths are undirected so no. of ways will reduce to (1000*999)/2 = 499500 )

In this particular example, we have a path exists between city 1 and 2, so the no. of ways will be 499500-1 = 499499.

Therefore, answer for this example is 499499.

I hope it helps you, if still you are unable to get it or facing some issue then please feel free to respond to this thread.

1 Like

Hi @sanjeetboora


Is it to be done so?

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

Awesome explanation…and this is not the first time… u have indirectly cleared my doubt… Thank u for ur amazing explanations!!!

1 Like