what does the values in the parent vector in disjoint dta structure represent?are they the immediate parents or superparents or can be any of the ancestors of that node at any given point of time while performing create set,union and find operations in disjoint set data structure.what about when all the operations have been completed?
consider the below example here the parent vector does not store the superparent after the completion of union operations :
number of sets initially=5
unions performed:
0 and 1
2 and 3
0 and 4
final parent array achieved
1 4 3 3 4
here 0 ,1,4 are connected and parent of 0 is shown as 1 and parent of 1 and 4 are shown as 4.how to solve this type of ambiguity in representative element of that component?
Parent vector in the disjoint set data structure issue
this is my second query ----find set operation in rooted tree implementation of disjoint set as given in the video takes O(1) amortized time when both union by rank and path compression is used .i can not understand how we have used union by rank i.e. getting the smaller tree appended as child to the bigger tree in the video code because in the video they have parent of superparent of x as y but it is not always the case that the component having superparent as x has smaller number of nodes .so where we have checked that we are actually appending the smaller tree ,if not how can we say that find operation takes O(1) time as we have not performed union by rank?
third query—please give the amortized analysis of find function in rooted tree implementation of disjoint set
fourth query—i have given the links of three codes that i have written for the disconnected cities question given in the video.please check if they are correct and also tell which code works the best if graph grows dynamically i.e. an edge is now to be added again and all the parameters need to be updated accordingly?
For your first query, it may be possible that the final parent array do not contain the correct superparent . because the approach we followed here is of path compression. so get_superparent() will give the correct superparent for it. You can use that function at the end to update the parent[] array.
For second query:- i didn’t get your doubt exactly, can you tell me the timestamp about which you are talking.
For fourth query:- If you just want to check which approach is wrong, you can also check it by submitting it on the problem.
About dynamically growing, Disjoint set Union Find algo is itself best when the graph is dynamically growing, as you can see in the code we are calling unite(x,y) for every (x,y) so it doesn’t matter whether you store all the (x,y) first then call that dsu OR just keep taking input (x,y) and along with calling unite(x,y)
If you want to read about the amortized time complexity of it, you can refer to the last slides of this link https://www.google.com/url?sa=t&source=web&rct=j&url=https://www2.cs.duke.edu/courses/fall17/compsci330/lecture18note.pdf&ved=2ahUKEwizotjFrdfpAhXTXSsKHdPwBHUQFjAMegQICRAB&usg=AOvVaw3eLIkM0uh-v2ebecK01_qp
Also if you want to read in detail about it then you will have to refer to CLRS book whose pdf you can easily find on google.
i am not able to see my second and third query --where is it?
@Rj.25
For amortized complexity i already shared some link above or you can also just google search it.
Now, I am summing up for all your queries.
Yes in the video, union by rank is not applied, if you will apply both union by rank and union by path, then the algorithm will become faster.
Actually, After applying the union by rank only the worst case complexity becomes O(logN)
Here we are talking about amortized complexity because the complexity for worst case will be still same but here our algorithm is reducing the chances of occuring of worst case. Think if the worst case is occuring only few times for some queries and O(1) for others then it will be great.
So after applying union by rank + path compression, it takes log * N for each union operation,where N is the number of elements in the set.
where log * N is the iterative function which computes the number of times you have to take log of N till the value of N doesn’t reaches to 1.
log*N is much better than logN, as its value reaches at most up to 5 in the real world. (so it is some constant not O(1) actually).
thanku sir for being patient and answering all my queries.would it be ok if i ask you a few more?
sir how to implement union by rank then?
also according to the union operation applied in the video(since it is not union by rank) what will be the worst case complexity of find operation and amortised complexity of find operation in this case as now the depth of the tree can be maximum n for n nodes?
@Rj.25
The amortized complexity will still be some constant but not that good, on combining both it is observed to be O(1). It is all practically observed and then explained.
for implementing you just have to add conditions in your union function based upon the size of the component of sets which you are going to unite.
if size of superparent of A > B then make parent of B as A.
else if A < B them make parent of A as B
else do any of the above step.