In the lecture video after connecting 4 with 3 (parent is 3) and 2 with 1 (parent is 1) we try to perform Union (4,1). Why don’t we directly draw an arrow from 1 to 4? Why do we need to consider the parent of 4 (i.e 3) into the situation at all? Why isn’t direct connection possible?
DSU 02- Union and Find Operations
It is Union (1,4) * sorry. Also in union operation is it necessary that the first element becomes parent?
The reason we don’t want to do direct connection is why we are using DSU in the first place.
Also Direct connection will lead to wrong results. See this example.
union(3, 4), 4 has parent 3 now.
union(3, 5), 5 has parent 3 now,
union(1, 4) 3 has parent 1 now.
So if I ask you the question whether 5 and 1 are connected , you can tell that they are connected. Because parent[5]->3 and parent[3]->1.
But if you would have simply joined 4 and 1, you could not tell if 3 and 5 are connected to 1( in less than linear time).
We are using DSU because a joined set can be represented by a single element. So any operations 4 does , we need to do it with its parent.
Also in union operation,the joining depends upon the conditions imposed by problem statement. But if we are not under any restrictions, we try to keep the bigger size element as parent.
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.