All students are saved by Indian Tutors on KZfaq. Thanks India !!

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.

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.

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!

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

Brilliant, really helps to watch your videos before reading about the topic at hand! Ty very much, keep up the good work :)

You can have a special talent of making anything complex look very simple. Thanks Tushar

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

Perhaps the most helpful disjointed sets video I've come across so far, thank you!

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

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

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!!

Thanks! This is helping me get through my cs class in college

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!

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.

The video made my day... Was stuck in disjoint sets for 1 day. Keep it up :-)

you are THE BEST Sir.. These are best videos on algorithms and data structures.

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

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

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

.. great help for me as well!! Even more descriptive than the chapter in Cormen´s Algorithms..thanks a lot for your support!!

This is the best explanation available on internet

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

Excellent Tushar, this solved my doubt :) . Was stuck for last 2 days !!

Great work !! Very nice and simple to understand explanations !

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

helped me out big time once again. thank you!

Ótima explicação! Great work again.

after 5 year also your videos are great,,, i was not able to understand clearly in any video then i came here, , FINALYY DONE

Dude you are awesome. Continue the good work!

Best disjoint sets video, thank you for sharing.

Thank you for the explanation, it helped me a lot!

Very elaborate explanation! Thank you!

Tushar thanks, I finally learned all about ranking union. Very happy for your video congratulations, I will follow your channel now.

Thank you, now that i can understand even kruskal's algorithm in a flash. Great video ;d

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 🙂

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

My professor wouldn't explain shit in the lectures. Great video! It really helped!

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

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

Love your videos man!

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

Your videos are the best!

precise and good explanation. Keep it up the good work :)

nice video.........has definately helped me in understanding the concept of disjoint set

Very nice and well explained video !! gr8 job sir !!!

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.

Thank you dude what great explanation. Excellent video !!!

very good, very helpful, and understandable for me even though english isn't my first language. thanks for sharing!

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

Best Data Structures and Algorithms videos on youtube!!!!!!!!!!

Awesome explanation sir ! Gud work !

unbelievable clear and easy to understand.

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.

nice video to learn how to represent disjoint sets and operations performed on it

Can you please make a video explaining amortized analysis?

excellent ! This video saved me from failing my midterm

And thank you so much for this video it helped me in the middle of the night to understand this concept ❤

That findSet function with the path compression is so fucking clever, nice dude!

Great introduction! :D

Thank you! you made it simple!

Thank you for your video, now it makes so much more sense to me! I have a question what if the findset number is the root, does the map just not change at all?

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'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?

Thank you so much, Ray William Johnson!

beautifully written code.. so simple.

Thank You for awesome explaination

thank you very much,you are explaining the material very good

tushar bro,really great video :)

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 :)

So much good explanation 🤗

This video is criminally underrated

The best explanation!

Your code is so clean!

simply awesome bro..

Great Tutorial !! Thanks

good tutorial, keep the good work

best explanation, made it simple!

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

Thank you, Tushar :)

Simply amazing!

great explanation, thanks

Hello Tushar, my name is Manar and I wanna thank you!

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

Excellent videos dude

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?

U save a lot of time... Tqs man.

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

Such a Great video

Thanks a lot Tushar

Interesting data structure :)

Excellent video.

Damn good explanation. :-)

very useful video ..helped a lot

Thsnks sir for amazing tutorial

superb explanation

When using path compression along with union by rank, the rank might be incorrect on application of the path compression algorithm. I have found union by size and path compression to be logically correct where path compression doesn't affect union by size at all. Any thoughts on this ? Would appreciate if anybody can point out if I'm missing out on anything for Union by Rank + Path compression

Great video sir..! :-)