basically, if we are considering the edge(u,v) vertices u and v then the first step is finding the absolute parent of each of the vertices u and v and 1)if the absolute parent of these two vertices are different then a)if the rank of their absolute parents is the same then make either of the absolute parent points to another absolute parent, and increase the rank of the absolute parent which is pointed by the other absolute parent by 1 b)if the rank of their absolute parents isn't the same then make the absolute parent with lower rank to point to the absolute parent of higher rank and don't change the rank. 2)if the absolute parent of both the vertices is the same then a cycle has been detected return true.
GOOD JOB!! PLUS: rank!=height, only in some case both can be same other wise not. rank of individual nodes can be calculated and heights as well but the tracking of height of every node becomes harder and harder everytime path compression is invoked, so, rank is preferred thus Union by Rank. Below is a GFG problem. I am just trying to give you a better understanding. Input: 5 // number of nodes and nodes are 1,2,3,4,5 4 // number of queries to perform U 1 3 //query1 = union of 1 and 3 C 1 2 // query2 = are 1 and 2 connected (do they have same parent? ): ANS = no U 1 5 //query3 = union of 1 and 5 C 3 5 // query2 = are 3 and 5 connected (do they have same parent? ): ANS = yes Output: initial parent array! 12345 initial rank array! 11111 1 2 ::: are connected? : 0 3 5 ::: are connected?: 1 final parent array! 12141 final rank array! 21111
great explanation but I have one doubt: when we store the changed value of the absolute parent, do we also need to decrement the rank? like in your example, 3 -> 2 -> 1 -> 0, we point 2 , 1 and 0 to 3. But we don't change their ranks.. isn't that necessary?
Hi ! I was trying to solve the Codeforces's 1st problem from their DSU pilot course without ranking/path compression. I got TLE :(. Is it necessary to always implement rank? In your last video, you initialized all the vector values to -1, some people initialize it to the corresponding index value. Which approach is better?? Thanks in advance. You are my GURU
Why am i getting the vibe that using rank just increases implementation complexity more than improving time complexity. bcoz union is otherwise using find operation which is just compressing path further and the resultant union will be more optimal anyway where as the union with rank is simply not using find operation before doing union which might give us the O(1) complexity for union operation but no optimisation for further find operations. please tell me if i am wrong
Worst case O(N) and avg case will not be O(log N). Log N is very very less than N. Try to take larger values of N and see the difference. Log N can be true for a balanced tree structure.
I have 1 doubt. We are not changing rank after path compression, now at 18:50 adding edge (4,3) suppose 4 also having rank 2, now since 3 and 4 having same rank than we can add 3 as parent of 4 making rank of 3 as 3 but actually rank (height) of 3 after path compression become 1 instead 2 (we didn't changed that) and we are adding 4 having height 2 as child of 3 making overall height of 3 to 3 better will be making 4 as parent of 3 in that case height of 4 remain 2 i.e overall height of tree 2 not 3.. and if these process continues in case of large no. Of nodes than height will keep on increasing
in union_op function, why the first two lines are commented down? I think they are needed in the implementation! as we are not storing rank for each and every node! Am I wrong somewhere?
I think if we don't use those two lines, tree's height will grow faster as we are not adding the component to the parent but we are adding it to some other node!
Hi ! I have one question regarding the path compression. For the find operation, why do you not change the rank? Let's say we want to union two trees with equal rank 2. Then we want to union the leaf node(height 3) of the first tree and the node of height 2 of the second tree. The first tree after path compression will be height of two and the second tree remains the same. Here, since we arbitrarily select which tree is merged into which tree(both have same ranks), let's say the second tree with height 3 will merge into the first tree than it's obviously worse than the first tree being merged into the second. So I'm curious why we don't adjust the rank after path compression. Is it because adjusting the rank every time we do "find" operation takes much time and it costs another data structure since we have to keep tracking of the heights of each node? Thank you a lot as always!!
Maybe it is a bit late, and you already got the answer somewhere else, but I think this is a legit question, and should be answered here. You basically answered it yourself. Finding the correct rank is would be in O(n), because you need to check the distance of each node to the root. There are basically 3 scenarios, that can happen: 1) The compressed path was not part of the longest path: Then the rank does not change no matter what 2) The compressed path was part of the longest path, and there exists another path of that length: Then the rank also does not change 3) The compressed path was part of the longest path, and there exists no other path of that length: Then you would need to update the rank. So you have to find the newly longest path. And for that you must travel all paths, because all paths are candidates for the newest longest path. All path means all nodes, means O(n). Now the video states, that the find operation acts in O(log(n)) (Which is not exactly correct in a worst case analysis, only in an amortized analysis, but correct enough for the discussion). Going from logarithmic time to linear time is an exponential blow up, that we want to avoid wherever possible ;)
hi, how to solve such a problem: Suppose you have season passes for m train lines between n cities, with different expiry dates. A ticket lets you travel on the line between two cities as many times as you like, in either direction, from now until the ticket expires. How can you quickly determine the last date on which you will be able to reach any city from any other city using your passes? (a) Give a solution with the union-find data structure that takes O(m α(m, n)) time after you’ve sorted the passes by expiry date. (b) Give a solution that colours and re-colours the cities, that takes O(m) time after you’ve sorted the passes by expiry data. You need not prove your solutions correct. please give guidance or a solution
I do not understand why do we use union by rank instead of union by height? I felt union by height makes more sense, because find algorithm depends on the height but not on the rank(as rank is defined the maximum height the set can have). Correct me if am wrong, By the way, this lecture series is awesome, I am learning graphs for the first time. Thank you
Actually I have explained the reason for your query in the video itself. Please rewatch. Also, rank for the same height may be different and rank is not guaranteed to be equal to height always. So, it will be confusing to understand if you use the name rank by height.
I have similar doubt, lets say we have two trees, 3-> 2->1->5 (rank = 3)and 6->7->8(rank=2), now we did operation find(3,2) so by path compression the first tree would become 1->5,2->5, 3->5 (rank=3, height=1) now if we take the union of the two trees. According to ranks the height of final tree would become 3 but if we made 6 as parent of 5 then we could have achieved height 2. So why are we not doing like this if our aim is just to keep the height minimum?
Can you explain please what is rank of a tree? And how the rank of tree before compression and after compression remain same since the height of both trees are not equal.
Sir why we say log(n) consider the skew tree in path compression in the first traversal I will have to visit all nodes in the skew tree so it's TC why it's TC not said O(N) only ???
What if both tree has same rank ( in union by rank problem ) how , we will take the union... since max.( Rank(1) , Rank(2) ) is same but on taking union rank will become Rank+1 and that will not lie between Rank(1) and Rank(2) ...What do you say now ??
Line number 15 in code. 26:19 path compression. Dont this line affect the rank of the parent . You were not updating the rank of absolute parent when you are doing path compression. Please reply🙏
You are right... but let me explain you why we do not need to do this. 1. Let's change the rank Ex, set - 1, has skewed tree of 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank actually become to 1... but when we join set -1 with set -2 having, 5->7->8 where 8 is parent and logically this has rank 2... now think, if we join set - 1 (considering rank -1) to set- 2, each element of set -1 has to compress it path separately because all are them pointing to 1.. so when you find path of 4 then 4->1->8. so, path of 3,2 only compress when you find them... 2. DO not change the rank. same example, 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank is same.. NOw, under stand this logic, actually rank is saying, (higher the rank, more number of nodes have been compressed by it.) so, 4,3,2, -> 1 (same rank = 3) and 5,7 -> 8 (same rank = 2. ) when we join less rank with more, only 5,7 need to compress it path on next find operation. I don't know this is perfect example or not.. but I tried to explain as good as I can.
Sure :) I think you will get it himanshu coz I have mentioned explicitly that rank is not height of tree. It's just a different value altogether because we will do compression and so height will change but rank won't. As soon as we compress, everything changes :)
TECH DOSE is like... get the quality content and get the hell out of here... I don't want to bore with any intro and greedy stuff... i.e., the rap at last...lol
![NONT TANONT - ดอกไม้ที่รอฝน (spring) - Reimagined [Live Session]](http://i.ytimg.com/vi/nY2PsFZFEOg/mqdefault.jpg)
![หมานแต่ผัวเขา - แสตมป์ โตเกียวมิวสิค [ OFFICIAL MUSIC VIDEO ]](/img/n.gif)
most beautiful explanation I have ever seen and I think this channel is underrated
Thanks :)
I think this is one of the most detailed video on disjoint set
Heard so many videos on DSU path compression and union by rank but understood it first time. Thanks a ton!
Nice :)
i love how you focus on the WHY portion and the details of the problem..thanks ..it helped a lot
Finally I understood everything - what is union/find/find compression/union by rank/implementations. Thanks a lot sir for such great explanation!!
Welcome 😀
This is one of best explaination for this topic all over the internet. Hats off man👌
Great work explaining the Disjoint Set . Both the videos were crystal clear. Keep it up bro
kids binge watch netflix
legends binge watch TechDose :)
😂
Clear explanations, thank you for given such a wonderful video
So much help video 😊 I clearly understand path compression in disjoint set
Thank you so much sir😊 I'm very happy to watch this video
Welcome bro
best explaination so far. recommending to everyone
Thanks :)
Thank you so much for these videos sir. Forever grateful.
Welcome :)
Gr8 explanation.Hats off!!
Thank you. Simple and clear explanation.
Welcome
Thank you bhaiya for amazing explanation.
Great work, sir ! Your channel is so underrated :( , thank you so much !!!!!!!
Thankyou sir❤️❤️❤️ most beautifully explained👍
awesome explanation !!
thnx for continuing with graph series!!
Welcome :)
Damn, MAN, thank you, such a clear explanation
I am honoured :)
Best explanation ever...❤
You and code n code are doing a very good work. Lots of love from West Bengal.
Thanks
Too nice explaination ,thank you sir..
Very well explanation sir. Appreciate your efforts.
Great explanation!!
Also, we can store the size of dsu set in node struct so that we can also query the current size of a particular dsu set.
👍🏼
Well explained!
Awesome explanation!!
Thanks
Again... AWESOME content
Thanks :)
Very fruitful video with nice explanation, Thank you so much sir
Welcome :)
very good explanation!! Thank you :)
Welcome :)
Thanks to continue graph series
Welcome
Cryst and Clear explanation and god speed outro . : )
Thanks :)
Genuinely speaking , I been to soo many channels soo many sites but understand this concept Today thankzzzzz a lot sir u r such a gem ✨
Welcome 😊
@@techdose4u sir plz keep uploading videos ✨😇
thank you Surya..
great explanation.
basically, if we are considering the edge(u,v) vertices u and v then the first step is finding the absolute parent of each of the vertices u and v and
1)if the absolute parent of these two vertices are different then
a)if the rank of their absolute parents is the same then make either of the absolute parent points to another absolute parent,
and increase the rank of the absolute parent which is pointed by the other absolute parent by 1
b)if the rank of their absolute parents isn't the same then make the absolute parent with lower rank to point to the absolute parent of higher rank and don't change the rank.
2)if the absolute parent of both the vertices is the same then a cycle has been detected return true.
GOOD JOB!!
PLUS:
rank!=height, only in some case both can be same other wise not.
rank of individual nodes can be calculated and heights as well but the tracking of height of every node becomes harder and harder everytime path compression is invoked, so, rank is preferred thus Union by Rank.
Below is a GFG problem. I am just trying to give you a better understanding.
Input:
5 // number of nodes and nodes are 1,2,3,4,5
4 // number of queries to perform
U 1 3 //query1 = union of 1 and 3
C 1 2 // query2 = are 1 and 2 connected (do they have same parent? ): ANS = no
U 1 5 //query3 = union of 1 and 5
C 3 5 // query2 = are 3 and 5 connected (do they have same parent? ): ANS = yes
Output:
initial parent array!
12345
initial rank array!
11111
1 2 ::: are connected? : 0
3 5 ::: are connected?: 1
final parent array!
12141
final rank array!
21111
Wow ! Great Explanation sir .
This channel will be verified one day.
Keep working 🤞
Thanks :)
Thanks to master of Graphs
:)
awesome explanation..!!!
Thanks
Very nicely explained 👍 thanku
Welcome
Thanks so much!
Welcome
Thank you sir🙏
Welcome :)
Very good explanation...
Thanks
Hi , could you please give clarity about the time complexity O(log N)? How to calculate the time complexity?
Love From Bangladesh
Thanks ❤️
great explanation but I have one doubt:
when we store the changed value of the absolute parent, do we also need to decrement the rank? like in your example, 3 -> 2 -> 1 -> 0, we point 2 , 1 and 0 to 3. But we don't change their ranks.. isn't that necessary?
Tech Dose ka style hi kuch alag hai
Thanq bhai 😅
Neat!
awesome ! :D
:)
Best On TH-cam
:)
@TECH DOSE the height is not always max(a,b) if both the two sets have same height then during their union the resultant height increases by 1.
Thanks
Welcome 😀
When basically the union find is used other than cycle detection?
which software do you use to make blackboard effect?
Rank of a node is the number of nodes that point to it.
Like toh banta hai boss XD
Thanks
Hi ! I was trying to solve the Codeforces's 1st problem from their DSU pilot course without ranking/path compression. I got TLE :(. Is it necessary to always implement rank?
In your last video, you initialized all the vector values to -1, some people initialize it to the corresponding index value. Which approach is better??
Thanks in advance. You are my GURU
It's pretty easy to apply path compression :) you just need to use 1 word.
Why am i getting the vibe that using rank just increases implementation complexity more than improving time complexity. bcoz union is otherwise using find operation which is just compressing path further and the resultant union will be more optimal anyway where as the union with rank is simply not using find operation before doing union which might give us the O(1) complexity for union operation but no optimisation for further find operations.
please tell me if i am wrong
Is path compression like DP where we try to avoid repeated steps like here after finding its abs.parent we store it as our parent....
Thank you :)
It is not actually dp. But you can think of like that because you wanna know the result at once :)
Correct me if I m wrong, before Path Compression the average case would be O(LogN) because its a tree and worst case O(N)!?
Worst case O(N) and avg case will not be O(log N). Log N is very very less than N. Try to take larger values of N and see the difference. Log N can be true for a balanced tree structure.
What is the name of the drawing tool you use?
Is it available for Linux?
please explain O(log N) complexity after the path compression
Please read the proof for logN
I have 1 doubt.
We are not changing rank after path compression, now at 18:50 adding edge (4,3) suppose 4 also having rank 2, now since 3 and 4 having same rank than we can add 3 as parent of 4 making rank of 3 as 3 but actually rank (height) of 3 after path compression become 1 instead 2 (we didn't changed that) and we are adding 4 having height 2 as child of 3 making overall height of 3 to 3 better will be making 4 as parent of 3 in that case height of 4 remain 2 i.e overall height of tree 2 not 3.. and if these process continues in case of large no. Of nodes than height will keep on increasing
Please reply and clear this doubt
same is the doubt i refered striver graph series, gfg article and then this video no body is changing rank after compression :( which should be done !
in union_op function, why the first two lines are commented down? I think they are needed in the implementation! as we are not storing rank for each and every node!
Am I wrong somewhere?
Can you mention the line numbers in the code for others to get clear referance. Thank you.
@@techdose4u line no. 20 and 21 in sublime text!(not in github one)
@@techdose4u Please reply! is there anything wrong in argument?
I think if we don't use those two lines, tree's height will grow faster as we are not adding the component to the parent but we are adding it to some other node!
Sir, I am curious that why don't we change the rank after compression, as after compression the height of the root node will also decrease.
I already told that height and rank are 2 different things :)
Can you please explain why the time complexity is log(N)?
Please read this proof: en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find
So wrong in complexity analysis
Hi ! I have one question regarding the path compression. For the find operation, why do you not change the rank? Let's say we want to union two trees with equal rank 2. Then we want to union the leaf node(height 3) of the first tree and the node of height 2 of the second tree. The first tree after path compression will be height of two and the second tree remains the same. Here, since we arbitrarily select which tree is merged into which tree(both have same ranks), let's say the second tree with height 3 will merge into the first tree than it's obviously worse than the first tree being merged into the second.
So I'm curious why we don't adjust the rank after path compression. Is it because adjusting the rank every time we do "find" operation takes much time and it costs another data structure since we have to keep tracking of the heights of each node?
Thank you a lot as always!!
Maybe it is a bit late, and you already got the answer somewhere else, but I think this is a legit question, and should be answered here. You basically answered it yourself. Finding the correct rank is would be in O(n), because you need to check the distance of each node to the root.
There are basically 3 scenarios, that can happen:
1) The compressed path was not part of the longest path: Then the rank does not change no matter what
2) The compressed path was part of the longest path, and there exists another path of that length: Then the rank also does not change
3) The compressed path was part of the longest path, and there exists no other path of that length: Then you would need to update the rank. So you have to find the newly longest path. And for that you must travel all paths, because all paths are candidates for the newest longest path. All path means all nodes, means O(n).
Now the video states, that the find operation acts in O(log(n)) (Which is not exactly correct in a worst case analysis, only in an amortized analysis, but correct enough for the discussion). Going from logarithmic time to linear time is an exponential blow up, that we want to avoid wherever possible ;)
hi,
how to solve such a problem:
Suppose you have season passes for m train lines between n cities, with different expiry dates.
A ticket lets you travel on the line between two cities as many times as you like, in either direction, from now until the ticket expires. How can you quickly determine the last date on which you will be able to reach any city from any other city using your passes?
(a) Give a solution with the union-find data structure that takes O(m α(m, n)) time after you’ve sorted the passes by expiry date.
(b) Give a solution that colours and re-colours the cities, that takes O(m) time after you’ve sorted the passes by expiry data.
You need not prove your solutions correct.
please give guidance or a solution
I do not understand why do we use union by rank instead of union by height? I felt union by height makes more sense, because find algorithm depends on the height but not on the rank(as rank is defined the maximum height the set can have). Correct me if am wrong, By the way, this lecture series is awesome, I am learning graphs for the first time. Thank you
Actually I have explained the reason for your query in the video itself. Please rewatch. Also, rank for the same height may be different and rank is not guaranteed to be equal to height always. So, it will be confusing to understand if you use the name rank by height.
I have similar doubt, lets say we have two trees, 3-> 2->1->5 (rank = 3)and 6->7->8(rank=2), now we did operation find(3,2) so by path compression the first tree would become 1->5,2->5, 3->5 (rank=3, height=1) now if we take the union of the two trees. According to ranks the height of final tree would become 3 but if we made 6 as parent of 5 then we could have achieved height 2. So why are we not doing like this if our aim is just to keep the height minimum?
Can you explain please what is rank of a tree?
And how the rank of tree before compression and after compression remain same since the height of both trees are not equal.
Rank is not height. Initially it is the height but after compression, height is less than rank
@@techdose4u what is rank actually? please elaborate this. I am in confusion
@@abhishekjaiswal6492 just a way to make efficient union op
Sir why we say log(n) consider the skew tree in path compression in the first traversal I will have to visit all nodes in the skew tree so it's TC why it's TC not said O(N) only ???
Please read the proof for this :)
@@techdose4usir I saw one on wikipedia tooooo much maths haha but still thanks for nice video
@@sanjayjoshi8807 that's why I didn't explain :)
What if both tree has same rank ( in union by rank problem ) how , we will take the union... since max.( Rank(1) , Rank(2) ) is same but on taking union rank will become Rank+1 and that will not lie between Rank(1) and Rank(2) ...What do you say now ??
You can choose anyone to become parent and increase the rank of absolute parent by 1.
He has explained this in the video itself
In gfg practice this optimization reduced the time from 0.57 to 0.38 :)
Nice :) You count each milliseconds :P
@@techdose4u no the editor shows the execution time xD
Nice :P
@@aayush5474 please provide question link or name.. on gfg, i couldn't find it..
why we've joined 8 with 1 nd not 9 with 1?
6:38 why will the rank be same--> it shoulb have been 2 as there are three levels only now.
Line number 15 in code. 26:19 path compression. Dont this line affect the rank of the parent . You were not updating the rank of absolute parent when you are doing path compression. Please reply🙏
You are right... but let me explain you why we do not need to do this.
1. Let's change the rank
Ex, set - 1, has skewed tree of 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank actually become to 1...
but when we join set -1 with set -2 having, 5->7->8 where 8 is parent and logically this has rank 2...
now think, if we join set - 1 (considering rank -1) to set- 2, each element of set -1 has to compress it path separately because all are them pointing to 1.. so when you find path of 4 then 4->1->8. so, path of 3,2 only compress when you find them...
2. DO not change the rank.
same example, 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank is same..
NOw, under stand this logic, actually rank is saying, (higher the rank, more number of nodes have been compressed by it.)
so, 4,3,2, -> 1 (same rank = 3) and 5,7 -> 8 (same rank = 2. )
when we join less rank with more, only 5,7 need to compress it path on next find operation.
I don't know this is perfect example or not.. but I tried to explain as good as I can.
what is rank here? dont get it please help
the overall time complexity for finding cycle is O(nlog(n))? or something else ?
Yea
@@techdose4u thanks
I think you should uncomment the below line in union_op function:
fromP = find(fromP);
toP = find(toP);
Right. I think I have uncommeted. In the previous code I forgot to comment it :)
anyone can give a input and corresponding output..thanks advanced
can anyone tell what is the difference b/ w rank and height in this .. why rank is remaining the same??
Initially height and rank was same. But due to compression, height of tree changes but rank doesn't. That's the difference explained in the video.
@@techdose4u rank will always remain same irrespective of what graph is?
Why we add one rank, when both have equal rank? 17:01
So as to increase the rank of the resulting tree after union
i have a doubt is rank = height??
No
What is rank? Maximum height of the tree? or number of elements in tree?
Neither of them.
@@techdose4u Okay need to rewatch video
Sure :) I think you will get it himanshu coz I have mentioned explicitly that rank is not height of tree. It's just a different value altogether because we will do compression and so height will change but rank won't. As soon as we compress, everything changes :)
Why 9 at 4:48 has no relation with the absolute parent
And to be frank could you please explain little slow and more detailed as u did in the initial videos if possible.
One line solution : (1
oh
hey u into sprituality?
@@mayankverma8520 sometime spirituality has nothing to do with gods.......but research work with physics and GAN architectures.
@@veerabhimanyusingh779 what are you even talking about? you and MAYANK SHARMA???
@@shaquille.oatmeal8301 just remain confused brother........!
TECH DOSE is like... get the quality content and get the hell out of here... I don't want to bore with any intro and greedy stuff... i.e., the rap at last...lol
really appreciate this effort keep going bro🤍🤍🤍🤍
please what is the name of board you are using