Hello friends my name is Tushar and today

I’m going to talk about disjoint sets using union by rank and path compression. So

what is disjoint sets? Disjoint sets is a data structure which supports 3 operations

makeSet,union and findSet. makeSet is an operation to create a set with only

1 element in there. Union is an operation to take 2 different sets and

merge them into 1 set and findSet is an operation to return an identity of

a set which is usually an element in a set which acts as a representative of

that set. So what are the use cases of disjoint sets.Kruskal’s algorithm uses

disjoint set. We also use disjoint sets for finding cycle in an undirected graph.

There are few implementations of disjoint sets. The most popular one is

the one which uses union by rank and path compression to run this operations

efficiently. So in the next section let’s understand these operations and let’s

understand the algorithm which uses union by rank and path compression. Let’s

understand disjoint set operations with an example here. Suppose I have 7

different elements and all of them are in their own set so basically we have

called makeSet on each individual elements. So first operation I do is

union 1 and 2. So it means that 1 and 2 will be in

a set of its own and let’s say 1 is a representative of this set so basically

saying findSet 1 will return 1 and findSet 2 will also return 1.Next

we’ll say union of 2 and 3. So right now this is in one set and this

is in another set, so we merge these two sets together so this becomes something

like this and let’s say 1 continues to be the representative of this set so

findSet 1, findSet 2 or findSet 3, all of them will return 1. Next we’re

saying union of 4 and 5. So here 4 and 5 are in one set and let’s say

4 is the representative of this set. Then we are saying union of 6 and 7. So this is in a set of its

own and let’s say 6 is the representative of this set so findSet 6 and findSet,

findSet 7 will all return 6. Then we’re saying union of 5 and 6. So

merge the 2 sets in which,one of which is 5 and one of which is 6 so

basically we’ll merge these two sets together and this will become something

like this and we decide who will be the representative. So let’s say 4

continues to be the representative of this merged set. So findSet 4,findSet 5

findSet 6 and findSet 7 all of them will return 4 because 4 is the

representative of this combined set. Then we are saying merge sets 3 and 7. So

3 in this set,4 is in this set so we merge them together so this will

become something like this. So at this point all the elements are in the same

set and now we can decide who will be the representative of this set. So let’s say 4

continues to be the representative of this set. So findSet 1, findSet 2,

findSet 3,4,5,6 and 7 all of them should return 4 because 4 is the

representative of this combined set. So hopefully this helps you understand what

makeSet,union and findSet means for disjoint set. In the next section let’s

look at the implementation detail. So we’re going to represent our disjoint sets

using tree. Every node of the tree will have 3 three properties- rank,data and

parent. Rank is going to store their approximate depth of the tree, data is

going to store the actual data elements and parent is going to be the pointer from

child to parent. So let’s try again the same example. So first we call makeSet

on all the elements,7 elements we have. So it results in 7 different sets,all

the roots of the set are pointing to itself so the parent is pointing to itself, all

the ranks are 0 and the data is 1234567. At this point this nodes are not

connected to each other. So first we do is union of 1,2. So we come here and we’re saying

combine 1 and 2 into 1 set. So what we do is we check the rank of 1 and 2. The rank of

1 and 2 is same. So in this,in this case it doesn’t matter who becomes parent of whom.

So what union by rank says that make the guy who has higher rank the parent

and the guy who has lower rank the child. The reason behind that being that the guy,

it will keep the depth of the tree as minimum as possible which will improve

our time. So in this case they are same so it

doesn’t matter. So let’s make 1 as their,as the root

and 2 as a child so this is this and the parent of 1 continues to point itself.

Since if we combine 2 different,2 different sets of same rank,the new,the

new root will have a 1 rank higher. So this will become 0 plus 1 so this

becomes 1 and this is 0. Rank of non-root node doesn’t matter. Then,

then next we are saying union of 2,3. So we start from 2. We go to,

we find which set 2 belongs to so we follow the parent pointer so we reach 1 and

then we follow it’s parent pointer so that’s also 1. So 1 is the root of this

tree and 3 is the root of this tree.We check which has a higher rank, so union by rank says

that the one with the higher rank becomes a parent and other becomes

child. So 1 should be the parent and 3 should be the child. So this becomes

something like this. 1,2 this is this way and then 3’s parent is also 1

and 1’s parent is itself and then the rank for 1 does not change. So

rank for 1 continues to be 1. Next we’re saying union of 4,5. So again their

ranks are same so it doesn’t matter who becomes a parent so let’s convert that

into a tree,into,let’s combine them together. So rank here is 1,rank here is 0 and

this guy is pointing to itself. Then union of 6,7. So again by Union

by rank it doesn’t matter who becomes parent of whom. So let’s make 6 as a parent.

7 point in this direction and rank here is 0 and rank here is 1. Then we’re saying

union of 5,6. So at this point we go to the 5’s,we find the

representative of this set which is 4 so we follow the parent pointer so we

reach this guy and this pointer is pointing to itself so it means this is the

representative of this set and this is the representative of this set. Then we check who

has the higher,who has the higher rank. Again they have same rank so we merge them

together and it doesn’t matter who is the parent but let’s keep 4 as a

parent so this becomes something like this. 4,5,6,7 and since we merge two nodes,two sets

of same rank then the new rank will be 1 greater. So this is 2,this is 0.

Again for non-root node it doesn’t belong,doesn’t matter what the rank is

and then this is pointing to itself. At this point if someone says findSet 7,

so basically give me the representative of the,representative

element of the set which 7 belongs to. So we follow the parent pointer, we reach 6,again

we follow the parent pointer,we reach 4 and then we follow the parent pointer and

then it’s 4 itself so we know that 4 is the representive of this set. Again

there is a,here we do a small optimization. What we do is we do path

compression which means that now what we do is we make 7 point directly to

4. So we decrease the depth as much as possible and then make this guy point

directly to 4 so next time there’s a query for 7,7 can directly reach 4 and we

can find the root very, so we can find the representative element very quickly. So

7 now starts pointing to 4. Then we say union of 3,7. So we come here and we

come here,we start with 3,we find the representative element of this set.

So we follow the parent pointer,we reach this point and for 7 we follow the parent pointer

and reach this point.So we check who has a higher rank. So 4 has a higher rank.

So this becomes the child of this guy so let’s merge them together so this becomes

something like 4,5,6,7 all of them have parent pointer pointing

to 4 and then we will have this so that’s 1 and then 1 has 2 and 1 has 3

and this is 0,this is 0,0 and this is rank 2 and the pointer is in this

direction. So this our merged set at this point. So the rank at the route is

2 and the rank of the non-root node doesn’t matter but you can see the

pointer direction,direction of the parent pointers 2 to 0,0 to 4,3 to 0,0 to 4.

Now if someone says findSet 2 so give me the set which 2 belongs

to. So 2 goes to 0,following the, following the pattern pointer,then 0

goes to 4 and then 4 is pointing to itself so 4 is the set in which this

belongs to but also has a path of as a, as a,as a improvement we also apply path

compression so what happens is this starts pointing to 4. So next time if

there is a query for 2,2 can directly go to 4 instead of going via this route.Also

if there’s a findSet 3 so we go to 0 and we go to 4 and then

ultimately this will start pointing to 4 so that as an optimization. So in

the next section let’s look at the time and space complexity. Space complexity is

pretty straightforward. If there are n elements in the set,the space complexity

will be O(n). What about time complexity. So if there are ‘m’ operations

and if there are n elements,the time complexity will be O(m alpha n). So

there’s a proof in the CLRS book describing how this will be the time

complexity. Here alpha n is a very slow, slowly growing function and for all

practices,practical purposes alpha n is less than equal to 4. So this

will pretty much become O(4m) where m is the total number of operations which is as

good as O(m).So next let’s look at the code for this disjoint sets.I have a

class disjointSet. In there I have an inner class Node.Node has data,parent

and rank and we already talked about what each of them does and then I have a

map of data to know this will help us quickly and efficiently find the node

given the data. So I have 3 methods here, makesSet,union and findSet. So

what makeSet does is it creates set with single node so it assigns the data

in the node and then it points a parent to itself and rank is 0 and then we put

this data and node into the map. Then let’s understand what union and findSet

does using this examples. So I have two sets,one with rank 3 and 1 with rank 2.

The representatives of the set are 1 and 11. So now I’m saying union of 7

and 13. So we go to this method union,so first we do is we get the nodes for 7

and 13. So we go to the map and we get node 1 which is the node pointing to 7

and we go to map and get the node 2 for node pointing to 13. Then we call findSet

and try to get the parent for each of these nodes. So we go to findSet,so we

come to this point and then we get the parent so we go to 7.7’s parent is 5 and

then 5’s parent is,so 5 is not same as node so then we again go into a

recursion and findSet again so 5’s parent is 2 and then 2′ s parent is,again we

go into the recursion and so we call findSet again and 2’s parent is 1. At

this point 1’s parent is also 1 so we get into this if condition and we return

parent so by returning parent we are setting the parent of every node in the

path to 1 so that is a path compression so 2’s parent will become one 1,then

5’s parent will become 1 and then 7’s parent will also become 1 and we already

discussed this as a part of path compression. After applying path

compression this is how my set 1 looks. like where 5 points directly to 1 and 7

also points directly to 1. So then it, the line number 49 also returns

parent 1 which is 1 so then we go to, execute line number 50 and node 2 is,

node 2 is 13 so we call findSet and try to get the representative of set

2.So we again go to findSet and here parent is 11 and 11 is not same as 13 so

we again go into the recursion and here we pass node as 11 and the parent of 11

is 11 so we return parent and then it will come back here and we set 13’s

parent as 11 and then return 11. So we come here,come back to line number 50 and

parent2 is 11 so then we apply our logic for union by rank.This statement here

just makes sure that if the parents are same we do nothing because they are

already in the same set otherwise we check a parent whose rank is higher so

in this case parent1’s rank is 3 and parent2’s rank is 2. So parent1’s

rank is higher so we go into this if condition and we check did parent

1 and parent 2 have same rank so in this case parent1 and parent2 do not

have seen rank so we do not change the rank of parent1 and then we also set

parent2’s parent as parent1. So 11,now 11’s parent now instead of pointing to

itself now starts pointing to 1. This is how the final picture looks like

after we do the union of 7 and 13 so 11’s parent is now 1. Next let’s try

to do a find on 14. So we come to find findSet and then we pass 14 so in the

data so first thing we do is we get the node for 14 from the map and then we go

to findSet here. So parent of 14 is 12, so

parent is not same as node so we again go into the recursion and this time node

is 12,again parent of 12 is 11 so they are not same so again we go to findSet

and we go to 11. Parent of 11 is 1, again parent is not same as node so

we go on to findSet and then this time node is 1 and parent of 1 is 1 so

at this time we go into this if condition and return parent. So basically

we return 1. So while going back what we do is we set 11’s parent as 1

and then we set 12’s parent as 1 and then we also set 14’s parent is 1.So

this is how my tree looks like after findSet 14 is executed.14 points to 1 and

also 12 points to 1 and this is as per as we discussed for path compression. So

finally let’s run this code. So in the main I have created 7 distinct sets

and then I perform a union of (1,2),(2,3), (4,5),(6,7),(5,6) and (3,7) which means that

all the sets,all this distinct sets should be merged into 1 set. So when I perform

findSet from 1 to 7 all of them should give one representative element. Let me

quickly run this code. So as you can see I get all 4,so all the findSets

are returning,returning me 4,it means that all of them are in one set now. So

this is all I have to talk about disjoint sets. Please like this video,share

this video,comment on this video,check out my facebook page and also check out

my github link at github.com/mission- peace/interview/wiki.Thanks again for

watching this video.

but when we have union(1,5) then we will take only 1 findset and 5 or we will take 1,2,3,4,5. ?

you are not describing time complexity which is imp. giving solution to the problem but not defining time complexity think u also don't know to how to do it.

Simply put…

thank you so much

I know you already receive a lot of praise, but god damn you are good at this. Thank you.

Can you please upload the implementation of Ds with C++ below

??

Best disjoint sets video, thank you for sharing.

good tutorial, keep the good work

7:40 rank(6) must be 1

9:45 rank(1) must be 1

thank you so much !!!!

i have understand the whole video till 12 minutes then java came with hashmap and killed my C ++.

Hello and thank you for this tutorial. But there is something I want to mention. All the parent pointers of the roots must be null, this will help to find the root of each node using a while loop in O(h).

?I don't undestand how do you find rank

When you run through the path compression logic, shouldn't the rank decrease for each disjoint set when there is an optimization to be had? For example, when you first merge 2 sets, you might have a rank of 3. After you use findSet(), doesn't the rank fall back down to 1?

Rank is not optimal, let's assume one node A has 1000 children, one node B has 1 child, both of them have the same rank, you could choose B as new root since it's random, now all the 1000 nodes below A need travel two steps to root B and one node under A travels one step to B, but if choose A as root is optimal since all 1000 nodes only travel one step to new root A and only one node travels two steps to A. So if change the rank to weight as how many descendants the node has will be the best.

At around 8:20, before the path of 7 is compressed, the rank of 6 should be (1) instead of (0).

amazing

Great Tutorial !! Thanks

superb explanation

try to give code in cpp

Why do we increment the rank if the rank of two sets to be merged is same and don't increment when they are different?

very useful video ..helped a lot

I think rank of parent 1 should be incremented in else loop in java code from line 63 to 65.

danke für das hilfreiche video ahmed hussein

excellent video..cleared all doubts in very less time…thanks a ton sir…

helped me out big time once again. thank you!

This video is amazing. It's explained so clearly, and it was a great idea to showcase the theory first, and then demonstrate the implementation. Great work man!

perfect

precise and good explanation. Keep it up the good work 🙂

Thank you for the great explanation and clean code!!!!!

How to know how many disjoint set and how many elements in each set.

Please reply!!!!????

sir at 10:03 rank of should be 3 i guess

sir we want to please use hindi language plzzzz it will be best for most of th student

Thanks!

Thusssssssssssssssaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrr you rock!!

chhod do sir apse na hoga

Wow such a clean code , I think the code can be provided without hash maps . … Though Cheers Nice and Effective Tutorial. 🙂

Hi, thanks for your video. I'm wondering rank node 1 at 10:10 second should be 1 why you change it to 0 ?

Nice!

Your video is always the best, helped me a lot of algorithms that I tried hard to understand.

Just awesome. I did not get this much of understanding from ny book. thanks a lot.

Great video ! This video was handy while brushing up the basics of algos. Keep up the good work, really appreciate it.

Basically path compression will occur only during search for the first time

Impressed by your teaching skills 🙂 Thank you for the awesome videos.

should the rank of node of 4 in 10:57 have rank 1 after path compression?

why doesn't rank of one go down too 2 from 3 at 15:20 in the video?? Great Video Thank You so much!!!

Hi, first of all, great video. Very good explanation.

I have one question. Hopefully someone can explain.

For the representative node (root node), why can't we set parent as NULL? This way, we can simply check if parent == NULL to find out if current node is root. Is there a use-case where a self-pointing parent is needed?

Thanks in advance!

At 7:41, node 6 is marked with rank of 0. But 6 has a child (node 7). So shouldn't the rank of 6 become 1?

Vaia ,I want disjoint set implementation code with c++.

Can you please send the link of python code for the same.

I think in the step where node having value 1 comes under 4 as parent, 4's rank should be increased to 3 from 2, but you kept it 2 only and decreased the rank of 1 from 1 to 0. Please clear it.

great job sir

Really good explanation. Most probably, explanation would be better if you would speak slowly.

post the code in c++

people like you make this world a better place!

well taught video. best out there. please keep them coming.

Thanks!

Thanks a Lot Bro

Thank you!

At 7:51 shouldn't the rank for data element 6 be 1?

At 9:00 when 7 directly starts pointing to 4 instead of 6, shouldn't the rank for 4 decrease by 2. Instead of 2 shouldn't it be 1?

slowely explain sir

thanx it was really helpful, pls can you explain about the other implementation like kruskals and diskestra too.

https://youtu.be/ID00PMy0-vE?t=518 Sir, why will the rank of 6 not be 1?

How will I detect cycles? And why did u write rank of 6 as 0? U're calling 6 the parent of 7… By path compression… if both are zero.. Then how can I call that 6 a parent of 7? Please help me..

The Best.

How can i break a set into two disjoint set? Any idea?

why answer is 4?

Thank you! you made it simple!

I had the rank question too. If you have it pay close attention to the explanation at 15:21

shoudn't the rank of node 4 after last union operation be 3 instead of 2 at 10:00 ?

confused about the rank update part. also, shouldn't we update the rank when necessary when we each time call find function?

at 8:49, doesnt 4 become rank 1 again due to path compression?

When the path compression happens in findSet, there should be a change in rank in this case as well. Rank of root with data = 1 shouldl be 2. Although there will be no problem in this particular example but if instead of union(7, 13), it was union(7, 14) then due to path compression the rank of both the trees would change(the root with data 1 should be 2 and the root with data 11 should be 1) and after setting the parent of 11 as 1, the final rank of root 1 should be 2. But in this code, the rank is not getting updated which might lead to a problem in further unions which may involve a node in this component.

Amazing video! And the first person Ive heard use whom correctly in one go.. haha

Thank You for awesome explaination

This is the finest videos on disjoint set available on YouTube Thanks Tushar for great explanation just a minor error 9 instead of 1 rank will be 2

at 8:47 , why the rank for node 4 is still 2? I'm confused with the ranks

3:11 poop it is

All

students are saved by Indian Tutors on Youtube. Thanks India !!

Damn good explanation. 🙂

10:56 isn't the rank of node 4 becomes 1 (depth of the tree after path compression) ?

Thanks a lot Tushar

Very clear!

Technically the rank of 6 should be 1, while merging 5 and 6 at 7:42

You really made this one simple to get. Thank you.

hello friend 👋🏼

judging from the marker, this is not in india.

Best teacher!!

Hello Tushar Roy, in the end of this video, how did you make 4 to be the representative of the large set? which method and line of code does that? Would you mind walking me thru that process? I couldn't understand despite your explanations. Thank you so much :))

Thanks a lot for this video. BEST VIDEO FOR THIS TOPIC

Nicely explain sir.

this is the best Disjoint Set Union video in the whole youtube !!! at 7:52 rank of the ( 6 ) should be 1

Awesome!! nice one covering all I need to know about disjoint sets to be able to apply it into problem solving

One of the best executed implementation with superb explanation. Thanks a lot.

thank you sir

thanks bruh, see you soon

Wonderful!! The simplest explanation I have ever seen on disjoint set and union-find!!

was really very helpful

I think instead of creating Nodes to store parent and ranks we can directly use Arrays or HashMap(for random order elments) right for storing parents and rank?