Everyone, so in this video, I'm going to on the Union Buronga and part compression algorithm on one
example.
So in this video, we are given this graphic.
So I've just drawn this graph here and this is around Gary and this is the pattern there.
So I will tell you, you can how you can check if the cyclosporin in the graph or not.
We have added these edges in this particular order in there, just in the list to let us start building
over there, DSU, and we will try to visualize it.
OK, then we will get you added Eurogamer ones in the beginning.
We have to assume all the states are independent because we are picking the first edge, Barack Obama
won, so we basically connect zero and one, if not both, had both have the wrong ones in the beginning.
Both have the wrong one.
What we can do is we can we will enter the case.
Let me show you.
So in the union algorithm, you will find out the parent of zero is zero and the parent of one is one,
if you just call this method, find it.
If it will return zero four zero and it will return one for one to both of them, have a different parent
in the union.
Find the algorithm.
You will see if Francophiles one is less than two.
This is not the case.
Will enter the cell elkies will the parent of two equals two sons.
In that case the will become the parent of one.
So we will have something like this.
We will have zero that is now behrendorff.
But.
Next time we get an average one, go to.
So what happens?
Let's see, we find the parent of one zero two parent of everything was minus one in the beginning,
but parent of one is now zero.
Percent of zero is also zero.
And one, comma, two, we need to find parent of two.
So those was having a voluminous one here, that means two is better and of itself, parent of two is
to they know one is zero.
How do we unite them when we unite the country?
We say, let us go ahead now because the is a smaller sect, OK?
And this is a bigger sect.
Zero is now having a rank of two because we are one node here and there is a smaller sect because of
union by rank.
Will also get attached.
Would you like this.
OK, but we will also get the parent, as you know.
Next time, so we have scanned this particular image, non-cyclical, no.
They said this guy does a discount next time we go to documentary.
So two, comma, three.
Two trees having this values, actually minus one.
So we have not written anything that is minus one tree isn't now having.
Berendt.
There's no doubt itself and two is now having a parent veto.
What we do, we will attach to you directly with the veto like.
OK, if I just show you the code, what we are doing here.
We say we Barrandov office to the parent of S2, so it does do commentary to these as two parent of
three equals two as one.
So what is this one as well as nothing, but it is a parent of two.
When you are connecting the entity, the parent of two will now become the parent of three.
Because because of the logic that we have written, we have even scanned the search now the next we
get zero for the period of orders for itself and period of zero is.
Zero itself.
OK, so this this this value should be actually minus one here period of zero zero itself and its value
is also minus one.
OK, so this value is also.
This is minus one, minus one.
So both of them are different.
So parent of four is four and parent of zero zero.
If we want to merge them, that would mean the smaller nerd with the bigger nerd.
So support will also get connected directly under a needle like this or will also have a parent.
We are done with this edge, expurgated the edge, this this I just connected, OK?
Next we get that five, six.
We are talking about this particular age, OK, in this case.
Both have the rank one to five is having around one sixth is having around one.
So I forgot to update these ranks.
All the nodes that are connected and they will add one to the rank of zero zero do have a rank of five
till this point.
This number is going to be five.
OK, I pick this age five, six.
So this is another.
So what we have we have four zero one two.
This is one part of the graph and we have five, six and no, no cyclosporin, OK?
OK, let's make five as a parent of six or something like this to let us see what we have been zero
and one, so zero and one.
So yes, I will become a parent of six.
Six will now have a parent as five.
The parent of six would be No.
Five, and Ranko five would now become two.
Like this.
OK, so this is just done.
Next, we have to earn five to two in five well-connected.
What we will do is we will talk to and five are connected.
We will make five azer that a child of.
We will basically attach.
Five, comma, six here.
OK, so this is how you will see where the bad combination thing will come in future.
Now Styx is having a longer path to reach six, five, five, so you can take five.
W6 This is a smaller tree, this is a subtree we are not going to we are we started with five and we
connected with zero.
OK, this is how this ad is done.
Then you have to come on five now to come up, five to come.
Aviva's I think it's done.
Five, comma six is done to a five year old Jordan.
Now you have this age to six.
Now you can see if as soon as you pick this particular age, it do commentary.
This was also done.
They said as soon as you pick this particular age, you will end up getting a cycle.
Because if you find a parent of two, that is going to be zero.
And if you find a parent of six, when you make a call to find a parent of six, you do bad combination.
This node will move from this point to this point and the.
Or the next day, when you will find the parent of six, you will get this parent in one time and you're
going to parent of six is now also the parent of five is also zero.
And a parent of two is also zero U.S. who is having a parent, zero six is having a parent zero, and
you will end up getting that.
This graph contains the actual let me just run this called.
And you can see it contains, as I can look, and if I just remove this edge, you will see we won't
get a single.
Yeah, so we got the segmentation fault, probably because I'm not given the correct number of nodes
in the graph, so the number of nodes should be seven.
Let me build the code and run the now.
Look at this graph contained the cycle, and if I just combined out this edge and it underscored again.
So this does not contain a cycle because this is the edge that is creating a cycle, and you can see
this graph does not contain cycle.
And if you want, you can actually break the pattern that is well, so I can see four and equals to
zero I less than V I plus plus the old behrendorff.
I.
OK, and we can also bring that on, Gary.
Two, four and equals to zero i less than v i plus plus.
And I can see old Bankoff I.
And and let us see the output for this graph.
Yeah, so it's it's actually returning through from this point, so just let me just remove this edge
as of now.
So you can see this is.
This is the pattern today, though.
You can see all the nodes of the parent as zero except six, which as a parent of five.
And since we removed the last node to six, it canceled our call, which could lead to bad combination,
because if we just make this call here.
Let me just.
Joe, you if I just skip this particular statement, so that will not return, true, but that will
show you the parent.
Now you can see if we decides to say homosex.
The parent of six is also updated as zero.
And this also leads to bad combination.
And you can see the direct parent of six is actually little.
That is the thing I was telling you.
OK, so.
What happened earlier was the group was looking something like this zero, we have parent one, we have
we have a child four, we have a child who we have a child three.
We have five.
We have six.
When you add this age to common six.
So when you make a call to the find function for six, it removes this note.
From this point, you do want compression and it attaches here.
And you can see it says having a parent zero and two is also having a parent zero and you get cycle
detected and so on.
So we have removed the return true statement so that we come to the end of the cold.
And earlier, if before this step X was having a parent that was five and you can see the rank of zero
is seven in both the cases and the rest, all elements have a rank of.
That's all elements of Aramco, one or two.
If I was having the rank of two because the elements were included.
So this is not important to us.
You can even make it zero after the merger.
So it's only important when a particular node is the leader of the state.
Once it is removed from the leader position of the state, that does not matter.
So we will return.
True.
And that's standard.
Good.
So so I hope this thing is now clear, it was a bit tricky, I think, for the people who are watching
it for the first time, you will find it a little tricky.
But if you try run it, if you go through it carefully two or three times, you will definitely get.
That's all for this video, thank you was.