Comment down any questions below! Please give it a like and subscribe to support our channel. Cheers, Potato Coders 🙂

You forgot to mention you have to union the shorter tree into the longer tree! Otherwise the trees in a set of n elements can be up to n elements long (just a straight chain, instead of branching) and you don't get log(n) complexity.

Thanks for sharing! It's very clearly and efficiently explained!

This was actually insanely helpful in understanding the concept. Thanks!

Amazing video, very easy to follow, thank you! 🎉

Love it man, short and clear!

So practical and helpful video=) Thanks

Loved this bite sized explanation!

wonderful explanation! Thanks mate!

Wow, thanks a lot, great explanation!

Amazing! It's very clear. Thank you

Awesome video, thank you! Question though; isn't the find operation O(n) time? I'm reading around that it isn't until you use 'Union By Rank' that it becomes O(log(n)).

Perfectly explained. Thanks

under-rated video.. thanks for the explanation

Amazing! thank you!

Best illustration... please provide more content

It so simple and straight forward. Thanks you so much

This video has saved me many hours of my life. Thank you for this.

wow , i must say that this was really easy and nice video , really nice explanation

Thank you so much this is great!

Crystal clear and precise...Thanks!!

fantastic video! thanks!!!

Really clear and concise explanation. This video helped a ton.

Short and clear, thanks

There is a little technicality, that when you do find(x), you want to do path compression, by connecting each vertex on the corresponding branch (the branch where x is) to the root. This results in subsequent find operations being cheaper (and you only double your cost one time).

very clear! Thanks!

Thank you! This was very helpful

thanks a lot for explaining in few minutes.

I was always stuck with the implementation of UF, now I finally got it, thanks!

Thanks for the concise and easy-to-understand explanation!

Thanks bro, now I finally understand it for tommorow exam ;p

Awesome explanation, thank you!

bro... come back ur vids r so good 😭

best explanation every ! :D

Thank you very much. Nice video.

You explained it so well! Thank you for your video!

Solved my hours long quandary in 5 minutes. Thank you!

Thank you so much man

Excellent video, thanks!

Great explanation

THANK YOU!

How do you select the representative? I struggle to understand that part of it.

Correction, this does not run in O(logn), but in O(n). To get O(logn) optimization, you need to use union by rank or by size.

Great explanation. Was able to recall what I had learnt a while back. Thank you!

This video was great! definitely not something that's very clearly covered in alot of other sources

You got a video on path compression?

Best video I've found on UF. Thank you!

Good content!

Bro this topic is confusing AF, but at least this vid makes it somewhat understandable

Thank you

Thanks Mr. Tater.

To optimize it, the find function should set the parent of it's parent to find(x). (This will probably help a lot) function find(x): if Parent[x] != x: parent[x] = find(parent[x]) return parent[x] If I'm wrong please tell me.

Subbed 💛

good video

This video is so gud but looks like the channel ain't active anymkre 🥺💔 I really loved the explanation n quality so thankuu n hope u r doing well ✨

awesome

wow!

Thanks

The Big-Theta runtime for find() would be Θ(n).

beauty

algorithm was easy but you should write code and execute

Wer sieht das auch für's HAW Studium?

Python code: # WITH Path Compression def find(self, parent, x): # finds root or representative of disjoint-set/union if parent[x] != x: parent[x] = self.find(parent, parent[x]) # path compression step return parent[x] def union(self, parent, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) parent[root_x] = root_y # WITHOUT Path Compression def find(self, parent, x): # finds root or representative of disjoint-set/union if parent[x] != x: return self.find(parent, parent[x]) return parent[x] def union(self, parent, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) parent[root_x] = root_y

There are two issues here: 1. When performing union, you set parent of the smaller set to the representative of the larger set. 2. When finding a path, you compress the path on your way back, improving O(logn) ops to O(log* n) in average.

This really didn't make sense