how to do the problem using bfs and dfs? pls can I get some hint
About the other solutions
hello @Senjuti256
the idea is simple run a dfs from each univisited node to find number of nodes in that component .
let say on dfs u visited c nodes. then count of required pairs will be c * (n-c) .
c is the count of nodes that are in current component.
n-c will be remaining number of nodes.
now if we pick one node from c and other node from n-c then they will be not connected becuase they are in different components.
repeat this process for all univisted node and add c*(n-c) to ur answer.
at the end print answer/2 (divide by 2 becuase each pair will be counted twice)
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.