Please help me i am not able to pass all tc for Pairing problem

#1

This is my code —>https://ide.codingblocks.com/s/358384

#2

hello @kailash_01
ur approach is correct but implementation is bit time taking due to this nested for loop
this is making ur time complexity O(N^2) where n is no of nodes.

image

to avoid this u need to observe this.

if c is the number of nodes in current connected components then n-c will be in some other components right?
that means if i pick one node from c and other node from remaining n-c there will not be any path between them because they are from two different components right.
so total how many combination are there ?
it will be c * ( n-c)
so u just have to run dfs to calculate count of nodes in each connected components ( say c ) and then u need to add c *(n-c) in ur answer .

at the end print ans/2 because each pair will be counted twice.
this will bring time complexity to O(n)

#3

but its not Giving TLE only WA

#4

it will give tle as well. try using long long.

logic i already explained

#5

It Still Giving WA :frowning: -->https://ide.codingblocks.com/s/358402

#6

pls wait bro .
i will debug it and will let u know ur mistakes

#7

@kailash_01
consider this case
10 2
0 1
0 2

here in ur map u will only have entries for 0 , 1 , 2 right?
but these are not the only nodes in the graph right? we have 3,4,5,6,…so on nodes as well and they willl also contibute to the result but becuase of the map they are not getting considered

#8

@kailash_01
check this->

explanation->