Pairing problem- graph

#1

how to approach this question. Got 1 test case right but I think my solution is totally wrong. can anyone help?

#2

@mikkyimran
Hello imran,
calculate connected components in given graph with their size(i.e number of nodes in connected coponent) and then simple pnc.

hint use union find

#3

ide–>https://ide.codingblocks.com/s/198853 tried calculating then no of nodes still getting wrong answer

#4

@mikkyimran
there is a logical error in ur code.

suppose we have two connected components .and let first component has n1 nodes and second component has n2 node .
then if i pick one node from 1st component and 2nd node from 2nd component then clearly there wont be any path between them right (and that is what we want).

so numbers of ways will be-> ways to pick one node from first component X ways to pick 2nd node from 2nd component

=> n1 * n2

now u need to extend the same logic when u have more than 2 connected components.

check reference code here -> https://ide.codingblocks.com/s/198865

#5

can it be done without using union find method?

#6

@mikkyimran
logic will remain same,
u can use dfs to compute number of components and number of nodes in each components .

#7

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.