Disjoint Sets using union by rank and path compression Graph Algorithm
ฝัง
- เผยแพร่เมื่อ 8 ก.ย. 2024
- Design disjoint sets which supports makeSet, union and findSet operations. Uses union by rank and path compression for optimization.
github.com/mis...
github.com/mis...
/ tusharroy25
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
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!
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.
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
people like you make this world a better place!
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.
You can have a special talent of making anything complex look very simple. Thanks Tushar
after 5 year also your videos are great,,,
i was not able to understand clearly in any video then i came here, , FINALYY DONE
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!!
Perhaps the most helpful disjointed sets video I've come across so far, thank you!
This is the best explanation available on internet
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
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.
Thanks! This is helping me get through my cs class in college
Wonderful!! The simplest explanation I have ever seen on disjoint set and union-find!!
So much good explanation 🤗
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 :)
Tushar thanks, I finally learned all about ranking union. Very happy for your video congratulations, I will follow your channel now.
nice video to learn how to represent disjoint sets and operations performed on it
you are THE BEST Sir.. These are best videos on algorithms and data structures.
Brilliant, really helps to watch your videos before reading about the topic at hand! Ty very much, keep up the good work :)
One of the best executed implementation with superb explanation. Thanks a lot.
Just awesome. I did not get this much of understanding from ny book. thanks a lot.
That findSet function with the path compression is so fucking clever, nice dude!
This video is criminally underrated
.. great help for me as well!! Even more descriptive than the chapter in Cormen´s Algorithms..thanks a lot for your support!!
And thank you so much for this video it helped me in the middle of the night to understand this concept ❤
thank you very much,you are explaining the material very good
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
My professor wouldn't explain shit in the lectures. Great video! It really helped!
great explanation, thanks
Thank you so much, Ray William Johnson!
excellent video..cleared all doubts in very less time...thanks a ton sir...
Your video is always the best, helped me a lot of algorithms that I tried hard to understand.
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
excellent ! This video saved me from failing my midterm
Thank you dude what great explanation. Excellent video !!!
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.
very good, very helpful, and understandable for me even though english isn't my first language. thanks for sharing!
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
unbelievable clear and easy to understand.
Great work !! Very nice and simple to understand explanations !
Impressed by your teaching skills :) Thank you for the awesome videos.
nice video.........has definately helped me in understanding the concept of disjoint set
this video was uploaded 5 years ago ,but still best 👍🏻 as compares with others
Very nice and well explained video !! gr8 job sir !!!
Excellent Tushar, this solved my doubt :) . Was stuck for last 2 days !!
The video made my day...
Was stuck in disjoint sets for 1 day.
Keep it up :-)
Best disjoint sets video, thank you for sharing.
best explanation, made it simple!
Ótima explicação! Great work again.
Thsnks sir for amazing tutorial
Good explanation
Thanks a lot for this video. BEST VIDEO FOR THIS TOPIC
I know you already receive a lot of praise, but god damn you are good at this. Thank you.
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).
Awesome explanation sir !
Gud work !
Interesting data structure :)
You really made this one simple to get. Thank you.
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.
Very elaborate explanation! Thank you!
beautifully written code.. so simple.
Can you please make a video explaining amortized analysis?
The best explanation!
Hello Tushar, my name is Manar and I wanna thank you!
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?
yes, cause when we will get the node and the parent and compare them then if the condition will give true cause they are equal and then we will simply return. Though I know you must not need this reply after 5 years but replying just to make you nostalgic
Your videos are the best!
Thank you, now that i can understand even kruskal's algorithm in a flash. Great video ;d
Very nice explanation
helped me out big time once again. thank you!
superb explanation
Nicely explain sir.
Thank You for awesome explaination
U save a lot of time... Tqs man.
Indian so great, they dominates the world of IT
Thanks a lot Tushar
Excellent video.
Thank you, Tushar :)
Love your videos man!
Thank you for the great explanation and clean code!!!!!
Well explained.
was really very helpful
awesome explaination
Amazing video! And the first person Ive heard use whom correctly in one go.. haha
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.
10:56 isn't the rank of node 4 becomes 1 (depth of the tree after path compression) ?
nice lesson
very useful video ..helped a lot
i have understand the whole video till 12 minutes then java came with hashmap and killed my C ++.
there is unordered_map in c++. duckduckgo.com/?q=unordered_map+c%2B%2B&t=canonical&atb=v55-1&ia=web
Why he set a map to a hashmap, instead of defining the variable as a hashmap to begin with?
Then I must say you're not good in C++ also.
@@a55tech Map is an interface in java.util. You can consider an interface as a blueprint of classes. HashMap is a class that implements the interface.
Since every HashMap is a Map, his way of writing isn't incorrect. He could have done what you're saying, but his method required him to type 4 less letters :)
I once gave a lecture in university and I thanked the Indian students for their help
precise and good explanation. Keep it up the good work :)
Excellent videos dude
simply awesome bro..
Your code is so clean!
While tail-end recursive loops and do-while loops are functionally the same in high-level programming languages it is always better to use a while loop from the assembly language point of view. The compiler has a much easier time with unconditional branches and counters instead of the mess of making a recursive loop. Just thought you should know.
good tutorial, keep the good work