Union Find - Union and Find Operations

Learn about the Disjoint Set (Union Find) union and find operations.

Related Videos:

Data Structures Source Code:

====================================

[terrordoger]

I found myself losing track of his train of thoughts or mid sentence sometimes, playing this at 1.5 speed really helped me understand it better!

[gabrielahernandez]

this is literally saving my life and WAY easier to understand than the class I'm taking lol. thank you!!

[krood_]

It pains me to see good videos like this are hidden in the algorithm while shitty videos with no efforts have so many views. Keep up the good work william.

[rhusselcombo]

🎯 Key points for quick navigation:

00:01 *🔑 Explains the union and find operations in a union-find data structure.*
00:17 *📝 Creates a bijective mapping between objects and integers to construct an array-based union-find.*
01:05 *🗃️ Stores the mappings in a hash table for efficient lookup.*
01:34 *📐 Initially, each node in the array points to itself as a root node.*
02:30 *🔗 To unify objects, the smaller component's root node is set as the parent of the larger component's root node.*
04:34 *🧰 Explains the process of merging smaller components into larger ones during unification.*
06:24 *🌳 If two objects belong to the same component, no unification is needed.*
07:42 *🔍 To find the component an element belongs to, follow the parent nodes until reaching the root node.*
08:41 *🚩 The number of components equals the number of remaining root nodes and never increases.*
09:48 *⚡ Path compression, covered in the next video, improves the time complexity of union-find operations.*

Made with HARPA AI

[scriptkiddie]

Man you are so underrated, you create amazing videos with concise explaination.

[ale-hlpg]

Thanks man, just by listening to you and listening to you and seeing the illustration it kind of nailed the point to me, that union-find is pretty much just a generalization of grouping. Not necessarily "grouping" as some specific algorithm, but any problem that you come across which can be solved by grouping elements together like Kruskal's MST

[ahmad-ali]

Classes are hell; this is much easier, thank you.

[lfhao]

good video, 1.25 speed makes it perfect.

[kartikxramesh]

Path compression is what makes Union Find an absolute *BEAST* of a Data Structure xD

[akshatbhutra]

Very nice concept of implementation of kruskal using union-find

[DillonHuff]

Thanks for making this video. It was very helpful!

[caboosept]

Good video! Helped understand everything

And I watched in 1.0x 😂 i dont know why people find it hard to understand

[advandizdarevic]

Maybe I'm missing something but at 3:44 we are grouping the elements and shouldn't there be a pattern to who becomes who's parent ex. the lower ID becomes the parent or the first element that we pass to the function is the parent? Because first two examples are (C, K) = (4, 9) = 4 is parent (lower id ), second example (F, E) = (0, 1) = 0 is parent ( lower id ), and then in the third one (A, J) = (5, 6) = 6 is parent? I know this is not the point of the video but shouldn't it follow the same logic if there's any? Later on it makes sense that we are merging the smaller component into the bigger one to flatten the tree. Great video overall didn't mean to be a party pooper :P

[greaterthanKTWS]

Hey, you went to my University! Awesome work!

[bharathateja]

all your videos are really helpful. thank you so much.

[spaceburgers]

these videos are really phenomenal I appreciate it!

[marilynmosala]

Awesome channel! So easy to understand!

[sallaklamhayyen]

great explanation
thank you so much🥰🥰

[emmanuelnsiah]

7:34 shouldn't c node point to e and shouldn't the index of 0 go to index of 4?

[terrordoger]

At 5:44 he said that because the orange component has more elements than the green component, how would the program know that when we're just performing Union(C, A), we would have to iterate through both subsets?