This code is giving wrong answer for following test case:
100000 2
1 2
3 4
Wrong answer for one test case
Algorithm-:
-> First step is to compute how many different countries are there.
-> Apply Depth First Search to calculate how many different connected components are present in the graph where the vertices are represented by the people and the people from the same country form one connected component.
-> After we get how many connected components are present, say M, we just need to calculate the number of ways of selecting two persons from two different connected component.
-> Let us assume that component i contains Mi people. So, for the number of ways selecting two persons from different components, we subtract the number of ways of selecting two persons from the same component from the total numbers of ways of selecting two persons i.e.
Number of Ways = N choose 2 - (∑(Mi Choose 2) for i = 1 to M)
For better understanding refer this -:
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.