Let's have a look at some of the Union find source code. So, here's the link to the source code. You can find it on my GitHub repository github.com slash William fees, slash data structures. I also have a bunch of other data structures from past videos. And before we dive into the code and make sure you watch the other videos pertaining to the union find, as I will be making some references to them. Okay, let's dig in.

Here we are inside the code. And I have a class called union find NCR few instance variables. So let's go over them. The first is size, just how many elements we have in our union find. Then I have these two arrays, one called ID and one called size. So the interest well the more interesting ones ID idea is that array I talked about which, at index i points to the parent node of AI.

And if Id at AI is equal to AI, then we know that AI is a root node. So we're essentially keeping track of all these like, tree like structures right inside an array, which is practical. And also because we create a by ejection between our elements, and some numbers, this is how we're able to access them through this ID array. And just for convenience, I track the number of components, test, sometimes some useful information you might want. So if you create a union find, well you need to know how many elements are going to be inside your union find. And I make sure that we have a positive number of elements otherwise I throwing an exception.

Then go ahead and initialize some instance variables. And I initialize ID to equal i. So initially everyone is a root node, and every component has a size of one. So find is pretty simple. It's given a, a node, it finds which component it belongs to, and also does path compression along the way. So if we're at p and wants to find the root node p, what we're going to do is we're going to find the root node using this one while loop.

So we initialize a new variable called root to P. And then we loop until the root is not equal to idea routes. So aka This is a root node or a cell phone. That we found so we can start and the root is stored in the variable called root. And then what we do is we do the path compression. This is what I talked about in the last video. So, starting back at p, we assign everything from idea p to equal the route.

And this is what compresses the path and gives us that nice amortized time complexity. You could also do this recursively, but I don't like having the overhead and doing things iteratively can be slightly faster. Okay, so, now, we have these simple methods, we can call so if p and q are inside the same component, this will return true because the root P and the root q will be equal otherwise We'll return false. And just calling find we'll do path compression. So even if we're just checking if two components are connected, and it calls the find method and we're compressing the path, same thing here, if we decide to find the component size relative to some index p, then when we index into the size and call find, we'll find Well, we'll find the root but at the same time, we'll also do path compression, which is nice.

And I would just like to note that the the root nodes are the ones who will always contain the size because they're the ones that are found Well, she won't think about it like at the end of the chain. Size this returns the number of components in our in find disjoint set components number components, self explanatory And the unifying methods, the last interesting method. So this is the one that well unifies two components together. So. So first what we do is we find what the root node for P is and what the root node for queue is. And if the root nodes are equal, then they're already in the same group and we don't do anything.

Otherwise, by convention, I just merge the smaller group into the larger group. Although I know some people like to keep the theoretical or largest path in a component, and then merge according to not that may be slightly more efficient, but it's more work. So I just like to merge the smaller group into the larger group. And also, since the roots are different, and we're in marriage, We know that the the number of components or sets must have decreased by one. So that's why at the bottom here, I say the number of components, subtract that by one, because we know we're going to have one less components. So this whole time inside this class, I've been treating P and Q as integers not as elements, like letters that I that we saw in our in the slides.

And this is because that by injection, I would do a lookup to find out what maps to the element p shouldn't give me an integer and what maps to the element Q and then I could use those with this union find data structure created, and turn everything into the realm of numbers instead of dealing with objects and having This is more complexity. It's much easier to have an array based union find. You could also have a pointer based union defined with node objects. But this is really nice and so really clean implementation. All right, that's it for the Yun find definitely my favorite data structure. And if you have any questions, just drop a comment and I'll try to get back to you.

So thanks for watching. I'll catch you next time.