Paring Problem in Graph Theory

#1

Using disjoint sets to solve pairing proble. However getting 1 wrong answer and 2 TLEs. Code is present at https://ide.codingblocks.com/s/181300

#2

give me some time i will check your code

#3

Hi tisan , there are some problem with your union find algorithm (disjoint set)

  1. In this question you only need to know two things number of sets and size of each set ,where a set consist of nodes that connected with every other node in the same set

  2. you don’t need to make whole graph cause the reason for using disjoint sets is graph operations are costlier .

  3. your implementation of disjoint sets is not correct ( as union operation(joining two different sets) should take O(log n) time and finding operation (finding whether given two nodes belong to the same set or not ) should take O(1) time

  4. your getParent and getRank in the worst case scenario can take O(n) time (in case of skew trees) that’s why you are getting TLE

#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.

#5

Hi! THanks for the comment, it was very helpful. However still I am facing some issue in TLE, so the code might be optimized more. My updated code is present at https://ide.codingblocks.com/s/184427. Can you please point where I can make the changes?

#6

Hi, you are getting TLE because in some cases your union - find algo can take O(n) time


This is a really insighful blog on disjoint set union .specially notice how they made sure that union operation will take O(logn) by storing the size of sets

In case of any doubt feel free to ask :slight_smile:

#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.