Graph - Pairing

#1

Can you please help me in optimising my code?

#2

@koshimagoyal97
Your code is having a Time Complexity of O(n * n*(n+m)),where n are the number of edges.
Lets see how:As you are using for into for over the size of list wherein list have size=n,and inside n you are calling hasPath which itself have time complexity of nm,
Total=n * n(n+m).
Now we have to do in nlogn or n.
What we can think is,the number of ways of selecting a pair is similar to getting connected components in a Graph.Let me elaborate further,
Consider 5 3
0 1
2 3
0 4

Here,by drawing on paper we can see 4-0-1 and 2-3 are two connected components of size 3 and 2 respectively,hence 3*2 are total ways.
This approach will reduce time complexity to O(m+n).
Please Refer this:https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/
Come back with code with this approach and please Hit Like if i gave a satisfactorily explanation to your doubt.

1 Like
#3

Still not passing test cases

#4

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.