Hi, everyone.
So in this video, we are going to discuss about disjoint sets, why we are discussing this, because
we have seen in the algorithm we need a cyclodextrin algorithm.
So with the help of disjoined that we can detect cycle.
So how disjointed works.
So there will be three Operation IT Union and find and these are the corresponding definitions.
So you can reach the definition, but you will be able to understand the definition when we will take
one example.
So this is one graph.
A graph will be given to us, so first of all, what we need to do, we will call the function, Mique
said.
We will call function.
Makes it on all the witnesses call me, except for all the word for word, text one word, text two
or three, four, five, six and seven.
So after calling the Mxit function what it will do, it will create a set with one element.
So I'm going to create sets.
So that means this is one third one element, one set of one element, one set of one element, one
set of one element, one set of one element, one set of one element and one set of one element.
So what it does, it create it creates it with one element.
So since I have called make certain all the vertices it has created sets with one element.
Right.
This is the first thing that we need to do why we are doing this.
You will be able to understand when it will go through the whole video.
So after calling the Miksad what we need to do, we will call the function unión.
We will call the function union.
What union does is it takes to set and it merge them into one.
For example, if I am calling unión.
When Commodore.
So this one element belongs to the set, the element to belongs to this.
So what it does is basically it combined the set.
So it will combine and this is my new sect.
So remove one remove, too.
And this is our new set, one and two.
Right work find function.
Does it find the representative element for that sect?
So this site is containing two elements, one and two.
So if I can find one and if I go, I'll find two, then the answer should be same.
Answer should be same.
So what I am trying to say here is there must be one representative element that represents the whole
set.
So in that case, see here we have only one element so that one element represent the whole set.
Here we have only one element.
So this element to represent the whole state.
But this is our new set and this set contains two element.
So one element will be the representative element for that.
It let's say one element, one is Diddy presented to find one will give you the representative element.
Representative element is one find to what it returns.
It returns the representative element for that set.
So to belongs to the set and the representative element for this at this one.
So the answer will be one.
Right.
Let's take one more example.
I want to find the union for two and three.
What will be the union for two and three?
So two belongs to this third and three belongs to the third.
So if we will take the union, then it will be one khama two comadre right.
I will be adding myself to belongs to the third and three belongs to the set and we want to take union.
And where does the union take to third and merge them into one.
So I have merged them.
Now again this site is containing three elements.
So one element we need to pick one element as the representative element.
Let's say I am picking one as the representative element.
So find out when one belongs to the set.
And what is the representative element?
One only.
Find of two.
Who belongs to this set and for this said, representative development is one, so answer will be one,
find three.
Three belongs to the third and the representative element for this site is one Sudan.
Will be one.
So you understand what is the meaning of find?
Find will return you the representative element for that said.
Let's take a few more example, I want to find the union of four and five, so four belongs to the third
and five belongs to the third.
So we will merge them.
So this is our new set, four and five.
Right.
And again, we're trying to do since this spat, this set is continuing to element.
So we need to pick one element as the representatively.
Let's say forward is the representative element.
So what is final four to four belongs to the set and the representative element for this episode.
So let's wait for what will be final five.
Find five belongs to the third.
And the representative element for the status for the final five will be for next week when, for example,
I want to find the union of let's say five, let's say six and seven.
So six belongs to the third, seven belongs to the third, so union will merge them six and seven.
And again, it is containing more than one element.
So we need to pick one element as the representative element.
Let's say I am picking success.
They represented the element.
So what will be find of six?
It will be six.
What is kind of seven?
Eight will be seven.
So it will be six because seven belongs to the state now.
And the representative element for this sect is six.
So that's why six.
Simple, right.
Let's take one more example.
I want to find the union of, let's say five and six.
So where does five belongs?
So five belongs to the state.
This one, right.
Five belongs here.
And where six.
Six belongs here.
So we need to merge these two states.
So let's merge them.
It will become four, five, six and seven.
And again, this are is containing more than one element.
So we need to pick one element as the representative elements so either you can pick four or you can
pick six.
Let's say I am picking for.
So what is final four here?
Or find a five of six.
Five of seven.
All the answer will be four.
Right.
Find affordable before find five belongs to the set and the representative, so find a fight will be
fought and similarly find 06 and 07 will also be fought.
So that's why I have written Actovegin one.
Go ahead.
Now, let's take one more example.
I want to find a union of three and seven.
So there is three.
Three is present here, right?
Three is present here.
Where is seven?
So seven is present here.
So what we need to do, what the unions say is union say is to set and merge them into one.
So we need to merge them.
So we need to merge one, two, three, four, five, six and seven.
So this will be one, two, three, four, five, six and seven.
So Representative Element four, this is for representative development for this latest one.
So again, the site is containing more than one element.
So you need to pick one element as the representative element.
Either it will be one or it will be for it's our choice.
We can select one or we can select for let's say we are selecting for as the representative element
for this set.
Right.
So what will be fired off?
One friend of one will be one belongs to the state.
No representative element is for some kind of one will be for similarly defined of two forward firing
of three four final five before five of six will be four.
Five of seven will be for the firing of all the elements.
Is going to be food.
So what is fine, fine.
Basically, we'll give you the representative element for that said.
So all the elements is present in the set.
So representative element is hard to find for all the elements will give you a representative element,
which is food.
So I hope you have understood what is the meaning of Miksad, what is the meaning of a union and what
is the meaning of find.
Right.
These three functions are very important to understand for cyclodextrin.
So now we are able to understand these functions.
Right.
And one more thing to note here is whenever I am saying said said means component connected component
in terms of Grauwe certain means connected component.
So I am saying here that this is one set.
So this means this is one connected component.
This is one set.
This is another connected component.
This is another set.
This is another connected component.
So set and component they both seem.
So if I see two elements in the same set, two elements in the same set, for example, one, two,
three.
So let's talk about this.
One, two, three.
So one, two, three.
Dilli in the same set.
So that means I can say they lie in the same connected component.
That means there must have been few edges like one, two and three.
This is one connected component I'm repeating myself, said means component to element line seems that
means two elements in the same connected component.
So this is one set.
And the corresponding component, right, certain component, they both are the same.
So now what is the next step?
So we know makes it.
We know union, we know find.
We know how they will work.
Let's try to understand how we will write the code laid the law.
We have understood how it will work, how union will work, how fine will work.
But we also need to write the code for them.
Right.
So let's write the code for them, how the code will look like.
So here I have written the code for me, exact function, find the function and union function.
What we need to do, we need to take one at a.
To write the code for all these function, we need to take one at the name of the phrase apparently
parent bearing the name of the Eddys, basically parent daddy.
OK, so what is happening here is these are what this is vertex one, vertex two or three, vertex four,
five, six and seven.
So our first step was called the Miksad function for all the witnesses called mixed function for liver
disease.
And this makes it function.
What it is doing Behrendorff, i.e., is a parent of one is one.
Parent of two is to parent of three is three.
Parent of four is four.
Parent of five is five.
Parent of six is six.
Parent of seven is seven.
So that is the first step that we need to do.
Call the Miksad function for all the witnesses.
And this is the definition for the Miksad function.
So this is what X1 and parent of Vertex one is one itself.
This is Vertex two, parent of Vertex two is to itself.
This is Vertex three, parent of Vertex three is three itself.
This is the meaning of this line.
This is Vertex four, parent of Vertex for this four, parent of Vertex five is five itself, parent
of Vertex six is six itself, parent of Vertex seven is seven itself.
So that is the meaning of this line.
That is how we will be able to fill this parent.
Very simple.
Now let's do the same thing that we were doing earlier.
The first thing that we did was we take a union of one to remember.
We took Union of one Komada.
So let me show you what we will do.
We will do all the same things again.
You don't know when comatose, then Tucumcari then for Coma five and at last Tecoma seven.
So I am doing all the same things again with code right now.
We have written the code so we will see how the code will work.
So Union of one and two.
So for union, what I am doing this is Union X is one used.
We are calling for end of one what this friend of one find of means the representative element.
So one is here who is the parent of one one itself.
So that will be fine.
Will return you when what is kind of to, to itself find him is the representative element remember.
And then what you are doing, parent of phase B, so basically what I am writing, this is two and the
parent of two is now one and the parent of one is one itself.
So this is the meaning of a union.
In previous case I have written like this union means one, two and one was the representative element.
I remember when was Dedee presented development.
I have written previously like this, but how it will work and cold.
It will work like this for the union.
We will first find out the representative element.
So find functional function will return you the representative element.
This is only one element in the set.
So representative element is one representative element is to then parent of one is two.
So we need to update this parent, Eddie.
So what will happen here?
When will come here and rest?
All the values will be same.
So one, two, three, four, five, six and seven.
Right.
Parent of two is when one more thing that I want to say it is.
It doesn't matter whether the right parent of equals B or you.
Right parent of B calls A, you can write any one of them.
Now let's move ahead.
So now what we need to do is we need to find out the union for two and three.
So this is two.
Two corresponds to one.
And this is the conditional.
We have three.
Right.
So this history and three will point towards one now.
And this is our said one, two, three.
And one is the representative element.
And similarly, we are going to update this parent, Eddie.
So what parent would have done?
The parent of three is one, parent of three is basically one Andrest.
Everything will remain same.
So one one, four, five, six and seven.
So how I am doing this, what I am doing so I am calling the union function twenty.
So union exists to find two.
What find it too will return to find it will return me one.
So Disvalue find willerton.
Me one five out of three will return three, right?
This is the function, this is their definition of fine function.
So final table at entry and then what we are doing.
So one thing here we can write parent of A equals B or we can write parent off B equals E, so let's
do this because I have operated that in this way.
So let's consider this and not this.
So I'm updating parent of three to be one, parent of three is now one simple.
Let's take one more example.
The next one was basically we need to find out the union of four and five.
So Ford is independent, five is independent.
Now, let's make the connection.
Let's say Ford is the representative element.
So in in previous approach, we have written like this four and five.
And Ford is the representative element.
So parent of five is basically Ford that everything will remain same.
This will be one one one four, six and seven.
Let's take one more example.
We want to find the union of, let's say, six and seven.
So seven parent of 77, parent of six is six.
And we need to make them.
So let's say we are doing like this, how it will look like inside.
So I have six and seven, six as needed.
Presenter development parent of seven is basically six.
Everything else will remain same.
This will be six.
This will be four for one.
When.
Now let's take a union of five and six.
So various firefighters here.
So let me write like this, this is five.
This is four and very six.
So this is six.
We are to combine them.
Let's say I'm combining like this six and seven and how it will look like.
So it will look like this four, five, six and seven and four is the representative element for this
sector.
And here the parent of six, parent of six is now for the parent of six is now for everything else,
will remain same when one one four, four and six.
Now we need to find out the union for.
Three and seven, so various three threes here, two, then I have one, then I have three and seven.
So this is seven, let's say four is the representative element.
So this is six.
This is.
Seven.
And this is five and how it will look like and said one, two, three, four, five, six and seven
and four is the representative element.
So here what I have done, I have changed the parent of one to four.
So parent of one is for everything else will remain same.
So one one four four four and six parent of two is one, parent of two is one.
Parent of one is for a parent of one is for similarly parent of seven six.
So parent of seven is six.
Parent of five is four.
Similarly parent of three is one.
Parent of three is one.
So that's how the court will look like.
Right.
That's how we can write the code for me.
Exact function for me, exact function for fine function and for the union function.
Now how this will help us, that's the main thing, how this will help us in cycle detection.
Let's see how it will help us.
So this is the problem that we have solved in our last video.
Now let's see how this functions.
Megg function, fine function and union function will help us here.
So first of all, what we need to do, what we need to do, we need to call the function Miksad.
Right.
So let's call the function makes it so.
I am writing like this.
I'm calling the function makes it so this is not zero nor zero, not one or two or three, four, five,
six, seven and eight.
So make that function will do this three year old before this will be five.
Six, seven and eight.
This is the work of the Miksad function, second step, what was the second step?
We need to pick the minimum wage and we need to combine them.
So what is the minimum wage?
I think this is the minimum wage for minimum wage.
Eight.
This is minimum wage.
So what?
Take seven, Vertex six.
Vertex seven belongs to a different set.
Vertex six belongs to Friend Said.
So here, what will do?
We will call the function union.
Right.
We will call the function union and how to check whether this is safe or not.
Because the lie in different six belongs to the frenzied seven belongs to the friend said that means
six belongs to different connected component, seven belongs to different connected company.
OK, so one more thing that I want to tell you is C.
This is.
One connected component or one said this is another connected component or another set, if we want
to combine them, if we want to connect one edge between them, then cycle will not be there.
Right?
This is one connected component.
This is another connected component.
And we are connecting with the help of this edge.
We are connecting two different sets to different connected components.
So the cycle will not be there if this is your one third when a critical component, this is yet another
third, another connected component.
If you do this, if you introduce edge in the elements which belong to the same set, then there will
be cycles.
So this is the concept of cycle.
Cycle will not be there if you are connecting two different elements, the elements which belong to
different set.
So here I am doing cycle detection.
S..
Seven belongs to a different connected component, six belongs to different connected component with
the help of this edge, with the help of this age, I am connecting to sets.
So cycle will not be there.
So the cycle will not be there.
And I can connect to them.
I can connect them.
So this will be six and seven.
I will pick this age, mate.
I will pick this edge rest.
Everything will remain the same.
It.
Five, four.
Two, one and zero.
Now, what is the next minimum wage?
I am running out of time, so what is the next minimum wage here next to minimum wages too?
So too is present here, too, is present here.
You can pick any one of them in any other time picking this one.
Right.
So it it belongs to different set to two, belongs to a different set.
And this edge combines two different set or two different connected company.
So Cycle will not be there.
So let's connect them, let's pick this age and let's connect them.
So I am picking this age and this will be to accommodate the rest.
Everything will remain the same.
This is six seven.
This is five.
This is four.
I have picked up to two is here and this is one.
And this is zero.
What is the next minimum wage next to minimum wage to.
So where six six is here.
Where is five.
Five is here.
So six belongs to the friend said five belongs to defensed so connecting them will not create cycle,
connecting them will not create a cycle so we can connect to them.
So this will become five, six and seven.
At least everything else will remain same.
This is to create this is for this is one.
This is zero.
So what is the next minimum cycle after two?
What do we have?
I think we have four.
So we have four here.
We have four here.
We can pick any age.
For example, let's say I am starting with this one.
So very zero zero is here.
Where is when one is here.
So they belong to different set, different connected component and joining them will not create a cycle.
Joining them will not create a cycle so we can join them.
So let's join them.
This will be zero one arrest.
Everything else will remain same.
This is for.
Five, six, seven.
This is to come out now, the next minute is this one for so there two two is here, where is five?
So five is here.
So they belong to different sects.
So connecting them will not create a cycle.
So you can connect them.
So let's connect them.
This will be two, five, six, seven and eight.
So I have picked this age.
OK, I have picked this age.
And everything else will remain the same.
So this is for this is zero comma one now what is the next minimum wage?
So after all, what do we have?
I think we have six, right?
We have six so far, six where it lies.
So it is present here.
Where is six?
So six is also present here.
See eight and six.
Both elements, both vertex, lie in the same set.
So taking this will create a cycle.
I'm repeating myself.
Eight and six belong to the same set, belong to the same connected component.
So picking this edge will create a cycle.
How it will create cycle.
You can see this one, this one, this one and this one.
They will be cycle.
So you cannot pick them.
Right, because six and eight belong to the same set.
So he cannot pick six.
Now let's move on to the next with next to it is I think seven.
Right.
I have seven here and I have seven here.
So let's check where those eight lies.
So eight is present here where those seven lies.
Seven is also present here.
Right.
Again, same set element belong to the same set.
So you cannot pick this because it will create a cycle.
Let's talk about this seven now.
So where does to present to is present here.
Various three.
Present three.
OK, we're sorry, OK, sorry, I basically forgot to write three here.
I forgot to write to you, so sorry, please forgive me.
So let's start.
So I was saying to is present here and trees present here, they belong to different set, different
set means, different connected component, and we are connecting to different connected components.
So cycle will not be there.
So we can pick this.
So this will become let's connect three here.
So this will be two, three, five, six, seven and eight and everything else will remain the same.
So this will be four and this will be zero seven.
Now let's pick the next minimum wage.
So after seven, I think I have eight.
So it is present here.
It is present here.
So let's pick in any order.
Let's say I'm picking this one.
So very zero zero seven zero is here in this area.
Seven seven is in the set.
So we can take this edge.
So let's take this edge.
Right.
So I'm writing here, let's combine desert, certain desert, because euro is present here and the seven
is present here.
So connecting them will not create a cycle.
So this will be zero, comma one, then two, three, five, six, seven and eight.
And I have selected this edge and four will remain same rate.
We have four, so four will remain same.
Now let's pick the next minimum.
So which is this one.
Eight.
So one.
Where is one.
Where is two, one and two.
The present in the same side.
So you cannot pick this because it will create a cycle.
How it will create a cycle.
You can see this one then, then basically this, then this, then this, then this and then this cycle
will be created.
So it cannot pick this.
Now after eight, what is the next minimum?
Next medium is, I think nine.
Right.
So three and four, they belong to different set.
So three is here for is here.
They belong to different set.
So connecting them will not create a cycle so you can connect them.
Zero one, two, three, four, five, six, seven and eight.
Right, so you have connected them after nine.
So after nine, what is the next minimum?
I think this has been so for 10, four and five, so zero five zero, you cannot pick this next after
10, we have 11 so far.
Eleven one and seven.
So when is it seven is here.
You cannot pick this.
So now 14 so far, 14, three and five.
So threes here.
Five is here.
You cannot pick this and that's it.
We come to the end of the algorithm and what do we have.
We have one set.
One set means one connected component.
And what is that one connected component.
That one connected component is basically from zero.
I have one I have seven six, five
to eight, three and four.
Right.
So that's how that disjoint set will help us in cycle detection encryption algorithm.
So I hope you have understood the complete algorithm, complete disjoint how this disjoined is working
during is working.
First of all, why did we call the function Miksad on all the vertices then what we are doing, we are
calling the union function and we are calling for end function.
Basically union function is calling finde function.
Right.
So I hope you have understood completely and now you have also understood what is the why.
I'm saying certain components.
Same because they are saying.
Right, so if to eliminate lies in the same set, that means they will lie in the same connected component,
that means cycle will be there, right?
So what is the final conclusion?
Final conclusion is if the element lies in the same set, same set or connected component one and the
same thing, then there will be cycle else, no cycle else no cycle, because they lie in different
set, because they lie in different set and you are connecting two different sets or two different connected
components.
So this edge, this edge will not create a cycle.
So that is the complete algorithm.
So in next we do what I will do.
I will write the code for the Kruskal algorithm.
So this is it from this video.
Guys, if you have any doubt, I know this this algorithm is a little bit complex at first.
You will face like few challenges.
You will find it difficult to digest.
But after watching the video once or twice, after going to the corridor after after training these
examples, you will be able to understand it very easily.
This is very, very simple overtime rate.
So since we have learned anything, we have learned, Disjoined said we have learned three functions,
makes that final function union function.
We have learned a crucial algorithm.
So it's a lot of things that we are learning at once.
But after like some time after one or two, that it will sink in.
So and next we do what I will do.
I will write very simple code for I'm still worried.
I'm sorry for Koskela algorithm for finding Misti.
So this is it from this video.
Guys, I will see you in the next one.
Thank you.