0:05 What is Disjoint Set? Disjoint Set is data structure that supports the following operations: a. make set: create a set with only 1 element in it b. union: take 2 different sets and merge them in one c. find set: to return the identity of a set Identity of a set is usually an element of the set that acts as a representative for it Use Cases: 1. Kruskal's Algorithm 2. finding cycle in an undirected graph 0:38 Implementations: 1. using rank and path - uses a tree - node: int rank int data node parent a. make set: 1. initialize n nodes with data and rank=0 2. make parent of all nodes point to the node itself b. find set(node): 1. dfs to a node that points to itself (root) 2. path compression: node.parent=root 3. return root c. union(a, b): 1. A=find set(a), B=find set(b) 2. if A==B => already in the same set 3. if(A.rank>B.rank) make A te parent of B and increments its rank by 1 vice-verse 11:07 Time and Space Complexity for m operations and n elements Space: O(n) Time: O(m.α(n)) ≈ O(4m) ≈ O(m) 11:57 Code
if A.rank > B.rank you shouldn't increment the rank. when both the sets are of same depth/rank only you have to increment the rank. if (A.rank > B.rank) B.parent = A; else if (B.rank > A.rank) A.parent = B; else { // both are equal so pick any B.parent = A; // A is the parent now A.rank++; }
Just a small little note: when he's saying 2 goes to zero (10:20), it should have been 1. He was reading the new rank of one which was zero (I just don't want anyone to be confused). Excellent video and explanation! Thanks a lot!
2 goes to real parent only when will perform find operation ,then all the member in the path will goes to main parent directly . this is will not the case for union. check code once
I already watched videos on union by rank and didn't quite understand why we're incrementing rank for a few cases and why not for other cases. Your explanation made it so clear! We'll increment rank only if both the sets are of the same rank, otherwise, we just make a union 🙂
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!
Wonderful video, very clear and very concise. My class didnt bring up "rank" but it really helped me understand. The use of code at the end was AWESOME
7:42 Rank of 6 will be (1) itself, only 4's rank increased to 2, but then as sir said, it won't matter what is the rank at the non-root node, we're never going to see them, so doesn't matter if its 1 or 0 or any other number. We're concerned only about 4's rank.
Not anymore. Abdul Bari is here to transform everything. Check his channel. He doesnt stammer and talks slowly and his videos are crisp. No offense to Tushar though
@@rohitk472not really, he jumps directly into say choosing dynamic programming or assuming that its greedy without explaining the reasoning behind it. There are many newer youtubers who explain things better.
Absolutely love your videos. I'm currently preparing for my interviews and your videos have been the go-to for me so far! Keep up the great work and thanks a million.
Tushar videos are fast and great but in this video another thing to notice is : 12.05 Tushar talks in native language and now we know he is desi guy :)
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.
9:03 rank of node 4 in second component should also have been 1 after path compression at 8:17 and therefore either component could be merged to the other while performing union(3, 7) at 9:03
I'm confused with the RANK. It seems that rank is determined by the higher ranked set when performing the union rank, i.e., union(set_m rank1, set_n rank0) results to be rank1. Does that indicate rank won't change as we keep attaching rank0 set to another set?
@@achuachu6296 Rank will change iff we try to union two elements of different sets having same rank . else the higher raked set will always be the parent of lower ranked set.
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).
All
students are saved by Indian Tutors on TH-cam. Thanks India !!
🇮🇳 I love my India!
Allah saves us all.....
I swear, every time I see Tushar walk in front of the camera I can't help but smile.
Thanks for being such a friendly and righteous dude.
0:05 What is Disjoint Set?
Disjoint Set is data structure that supports the following operations:
a. make set: create a set with only 1 element in it
b. union: take 2 different sets and merge them in one
c. find set: to return the identity of a set
Identity of a set is usually an element of the set that acts as a representative for it
Use Cases:
1. Kruskal's Algorithm
2. finding cycle in an undirected graph
0:38 Implementations:
1. using rank and path
- uses a tree
- node: int rank
int data
node parent
a. make set:
1. initialize n nodes with data and rank=0
2. make parent of all nodes point to the node itself
b. find set(node):
1. dfs to a node that points to itself (root)
2. path compression: node.parent=root
3. return root
c. union(a, b):
1. A=find set(a),
B=find set(b)
2. if A==B => already in the same set
3. if(A.rank>B.rank) make A te parent of B and increments its rank by 1
vice-verse
11:07 Time and Space Complexity
for m operations and n elements
Space: O(n)
Time: O(m.α(n)) ≈ O(4m) ≈ O(m)
11:57 Code
if A.rank > B.rank you shouldn't increment the rank. when both the sets are of same depth/rank only you have to increment the rank.
if (A.rank > B.rank) B.parent = A;
else if (B.rank > A.rank) A.parent = B;
else { // both are equal so pick any
B.parent = A; // A is the parent now
A.rank++;
}
@@reshmaarul8637 thanks man, lemme edit that
Just a small little note: when he's saying 2 goes to zero (10:20), it should have been 1. He was reading the new rank of one which was zero (I just don't want anyone to be confused). Excellent video and explanation! Thanks a lot!
2 goes to real parent only when will perform find operation ,then all the member in the path will goes to main parent directly . this is will not the case for union. check code once
Perhaps the most helpful disjointed sets video I've come across so far, thank you!
after 5 year also your videos are great,,,
i was not able to understand clearly in any video then i came here, , FINALYY DONE
people like you make this world a better place!
only if you walked through the code of every problem like you did in this one!! Great work Tushar! You're still helping people after 6 years!!
This is the best explanation available on internet
You can have a special talent of making anything complex look very simple. Thanks Tushar
I already watched videos on union by rank and didn't quite understand why we're incrementing rank for a few cases and why not for other cases. Your explanation made it so clear! We'll increment rank only if both the sets are of the same rank, otherwise, we just make a union 🙂
its a great one while all others left this concept you made it exceptional 👌👌👌👌👌👌👌👌
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!
Wonderful video, very clear and very concise. My class didnt bring up "rank" but it really helped me understand. The use of code at the end was AWESOME
7:42 Rank of 6 will be (1) itself, only 4's rank increased to 2, but then as sir said, it won't matter what is the rank at the non-root node, we're never going to see them, so doesn't matter if its 1 or 0 or any other number. We're concerned only about 4's rank.
Best Data Structures and Algorithms videos on youtube!!!!!!!!!!
Not anymore. Abdul Bari is here to transform everything. Check his channel. He doesnt stammer and talks slowly and his videos are crisp. No offense to Tushar though
Abdul bari is a beauty... He is a gem💎💎💎😍😍😍
@@AbhishekKumar-im2xd yes!!
@@blasttrash Tushar Roys explanation is top notch...
@@rohitk472not really, he jumps directly into say choosing dynamic programming or assuming that its greedy without explaining the reasoning behind it. There are many newer youtubers who explain things better.
Wonderful!! The simplest explanation I have ever seen on disjoint set and union-find!!
This video is criminally underrated
Absolutely love your videos. I'm currently preparing for my interviews and your videos have been the go-to for me so far! Keep up the great work and thanks a million.
Amazing explanation, cleared some little doubts I had. Thank you!
Tushar thanks, I finally learned all about ranking union. Very happy for your video congratulations, I will follow your channel now.
excellent ! This video saved me from failing my midterm
you are THE BEST Sir.. These are best videos on algorithms and data structures.
My professor wouldn't explain shit in the lectures. Great video! It really helped!
Tushar videos are fast and great but in this video another thing to notice is : 12.05 Tushar talks in native language and now we know he is desi guy :)
Thanks! This is helping me get through my cs class in college
That findSet function with the path compression is so fucking clever, nice dude!
this is the best Disjoint Set Union video in the whole youtube !!! at 7:52 rank of the ( 6 ) should be 1
Doesn't matter, we aren't really concerned about ranks of nodes other than parent's
One of the best executed implementation with superb explanation. Thanks a lot.
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.
Non-root ranks don't matter which Tushar mentions, since we'll only be merging using the rank of the parents
Brilliant, really helps to watch your videos before reading about the topic at hand! Ty very much, keep up the good work :)
This is the finest videos on disjoint set available on TH-cam Thanks Tushar for great explanation just a minor error 9 instead of 1 rank will be 2
Just awesome. I did not get this much of understanding from ny book. thanks a lot.
Your video is always the best, helped me a lot of algorithms that I tried hard to understand.
excellent video..cleared all doubts in very less time...thanks a ton sir...
The video made my day...
Was stuck in disjoint sets for 1 day.
Keep it up :-)
I know you already receive a lot of praise, but god damn you are good at this. Thank you.
.. great help for me as well!! Even more descriptive than the chapter in Cormen´s Algorithms..thanks a lot for your support!!
Awesome!! nice one covering all I need to know about disjoint sets to be able to apply it into problem solving
Great video ! This video was handy while brushing up the basics of algos. Keep up the good work, really appreciate it.
nice video to learn how to represent disjoint sets and operations performed on it
9:03 rank of node 4 in second component should also have been 1 after path compression at 8:17 and therefore either component could be merged to the other while performing union(3, 7) at 9:03
So much good explanation 🤗
Excellent Tushar, this solved my doubt :) . Was stuck for last 2 days !!
very good, very helpful, and understandable for me even though english isn't my first language. thanks for sharing!
And thank you so much for this video it helped me in the middle of the night to understand this concept ❤
Great work !! Very nice and simple to understand explanations !
Thank you dude what great explanation. Excellent video !!!
unbelievable clear and easy to understand.
Thank you so much, Ray William Johnson!
thank you very much,you are explaining the material very good
You really made this one simple to get. Thank you.
Very nice and well explained video !! gr8 job sir !!!
Best disjoint sets video, thank you for sharing.
nice video.........has definately helped me in understanding the concept of disjoint set
Thank you, now that i can understand even kruskal's algorithm in a flash. Great video ;d
great explanation, thanks
Awesome explanation sir !
Gud work !
Thanks a lot for this video. BEST VIDEO FOR THIS TOPIC
Dude you are awesome. Continue the good work!
helped me out big time once again. thank you!
Very elaborate explanation! Thank you!
Hello Tushar, my name is Manar and I wanna thank you!
Ótima explicação! Great work again.
best explanation, made it simple!
Amazing video! And the first person Ive heard use whom correctly in one go.. haha
10:56 isn't the rank of node 4 becomes 1 (depth of the tree after path compression) ?
at around 9:45, why does the rank of node 1 become 0?
Rank does not need to be accurate.
because for non-root nodes it doesn't matter what the rank is... The rank of the root node is the one that is important.
Rank should be 1 as we can see in java code.
I think its a mistake
Yes, it is a mistake. The rank would not change.
precise and good explanation. Keep it up the good work :)
Thank you for the explanation, it helped me a lot!
Your videos are the best!
Thank you for the great explanation and clean code!!!!!
Love your videos man!
beautifully written code.. so simple.
this video was uploaded 5 years ago ,but still best 👍🏻 as compares with others
tushar bro,really great video :)
Thsnks sir for amazing tutorial
U save a lot of time... Tqs man.
Indian so great, they dominates the world of IT
Thank You for awesome explaination
The best explanation!
I'm confused with the RANK. It seems that rank is determined by the higher ranked set when performing the union rank, i.e., union(set_m rank1, set_n rank0) results to be rank1. Does that indicate rank won't change as we keep attaching rank0 set to another set?
me too
@@achuachu6296 Rank will change iff we try to union two elements of different sets having same rank . else the higher raked set will always be the parent of lower ranked set.
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).
Very nice explanation
superb explanation
Nicely explain sir.
17:30 why the output is 4?
yeah, it should be 1
Can you please make a video explaining amortized analysis?
Interesting data structure :)
At around 8:20, before the path of 7 is compressed, the rank of 6 should be (1) instead of (0).
Your code is so clean!
Thank you, Tushar :)
simply awesome bro..
Good explanation
I had the rank question too. If you have it pay close attention to the explanation at 15:21
at 8:47 , why the rank for node 4 is still 2? I'm confused with the ranks
Hi, thanks for your video. I'm wondering rank node 1 at 10:10 second should be 1 why you change it to 0 ?
very useful video ..helped a lot
good tutorial, keep the good work
Thanks a lot Tushar