hey!..inside that union function what if the parent of u and v is already same...means they are connected to same parent...then we should be doing anything....right?.....see this (reference: en.wikipedia.org/wiki/Disjoint-set_data_structure) function Union(x, y) is
x := Find(x) y := Find(y) if x = y then return // x and y are already in the same set end if // If necessary, rename variables to ensure that // x has at least as many descendants as y if x.size < y.size then (x, y) := (y, x) end if // Make x the new root y.parent := x // Update the size of x x.size := x.size + y.size end function
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ? What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
In kruskal algo we check if parents of u and v are different and then only we call the union (u,v) .. since DSU is used at many places if someone tries this code as it is , it will lead to wrong answers. So for anybody reading this comment, always make sure before doing the union that the parent of u and v are different else if they are same no need of union as they already belong to same component.
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ? What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
Each And Every video till I watched, The explanation is so simple that I understand the concepts from a single play even though I watched videos in 2x 😄. Well Explained. Thanks for the graph series. Please make series on other topics too.
I believe in the Union function you could keep track of number of connected components…increment it if parent of u not equal to parent of v…if u and v same keep connected components same
You should have put a check in union that if(u != v) then only proceed for union otherwise it will do union for two nodes having same parent and will unnecessarily increase rank of one node
C++ Code : //check if 2 nodes are belong to the same components or not #include using namespace std; void makeSet(vector&parent, vector&rank) { int n=rank.size(); for(int i=0;i
The rank might change during path compression and we have not implemented anything in the findPar function to account for that change. We might be making sub-optimal connections in the union function if the ranks are unreliable
Refer Tech Dose video for this. His video will exactly clear your doubt. Striver's graph series is great, but in some concepts like this one, it is lacking intuition.
@@amanagarwal6897 even tech dose video on rank and path compression is not changing the rank during every path compression....you can find any article no one is changing the rank during path compression and the reason i got to know is changing rank would increase the time complexity !
i think the rank of the 1 will also be 2 coz 0 ---> 1 for the 2 node and 1--->2 for 3 node and another doubt is that the path compression will happens when it will be called like in this case union (*, 7) for the second time then only it will be effective but for the first time it will tranverse for logn times
Sir, have you made videos on heaps and priority queue also?If no,can you please make it sir. It"ll be very helpful.All your contents helps a lot. Thanks!
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ? What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
Just to reiterate the use of path compression. Is someone is still confused with the optimization- at 14:00 secs- using the same example- last query union (3,7) x= findParent(7); // 7->6->4->4->4 so finally parent is 4 after 4 hops y=findParent(3); // 3->1->1 parent 1 lets say we dn t do path compression we keep the parent array as it is in this step. Now the next step is UNION which says - lets suppose rank of x > rank of y parent[y]=x; rank of 4 is greater than rank of 1 that means parent[1]=4 now lets say we have another query (something,7) x= findParent(7); // 7->6->4->4->4 again we will have to make 4 hops if we would have done path compression then x= findParent(7); // 7->4->4 2 hops only.
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ? What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
When we compress the path,it can also change the rank of any node. Will this impact the logic or time complexity of the algorithm, since we are not handling this change in rank by path compression in our algo??
In the union operation if the parents are the same then we can just skip it right, rather than entering the else statement and increasing rank[u] by 1 like your code does?
I think not... because inorder to do path compression we need to have some sort of backtracking...which is not available in the iterative version of the function!!!
bhaiya for the challenge we have to send only one screenshot after we do all the challenge videos ? and the hashtag is to be used in linkedin while sending u the screenshot? or we can send it personally to your linkedin dm???
Suppose we have 4 vertices and their values: 55, 65, 22, 32. Now, we created a parent array of size 10^5. Cool. Because every vertex gets themselves assigned as their parent initially (i.e. index value will be same as the vertex value.) But, inside the makeSet() function, we're running the self-initialization loop for the COUNT of vertices i.e. 4 and not FOR THE vertices' value. Eg. In the parent array, we're initializing index 0, 1, 2, and 3 with the same value as the index i.e. 0, 1, 2, 3. BUT, our vertices are actually present at index 55, 65, 22 and 32 respectively which do not get initialized as we only ran the loop for the COUNT of vertices i.e. 4. So, shouldn't we run the makeSet() loop for all 10^5 elements. And, doesn't this brings a disadvantage of array space being wasted? :/ @take U forward
if i give u & v with same parent in union operation then the rank of their parent increases according to the union function written in the above code but no component was added, this should be an error. please make it clear to me if possible
after entering the function, the first 2 lines are used to make u as the parent of u and v as the parent of v, see u=findPar(u) v=findPar(v) so even if you write parent[u] = findPar(v), it won't change anything except calling the findPar() function once more and returning V itself
Can someone please clear my dount that in second last main, if statement if(findPar(2)!=findPar(3)) why cant we just check the parent array instead,i mean it do stores the parent right
I will be posting a video every Sunday on the other channel, so bell DABAAAAA dena: ua-cam.com/channels/vEKHATlVq84hm1jduTYm8g.html
hey!..inside that union function what if the parent of u and v is already same...means they are connected to same parent...then we should be doing anything....right?.....see this (reference: en.wikipedia.org/wiki/Disjoint-set_data_structure)
function Union(x, y) is
x := Find(x)
y := Find(y)
if x = y then
return // x and y are already in the same set
end if
// If necessary, rename variables to ensure that
// x has at least as many descendants as y
if x.size < y.size then
(x, y) := (y, x)
end if
// Make x the new root
y.parent := x
// Update the size of x
x.size := x.size + y.size
end function
and what about the time complexity of makeset.......O(n) is there....?
@@praveengautam9851 Same node will connect to his parent
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ?
What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
In kruskal algo we check if parents of u and v are different and then only we call the union (u,v) .. since DSU is used at many places if someone tries this code as it is , it will lead to wrong answers. So for anybody reading this comment, always make sure before doing the union that the parent of u and v are different else if they are same no need of union as they already belong to same component.
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ?
What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
Thank You So Much for this wonderful video..........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Each And Every video till I watched, The explanation is so simple that I understand the concepts from a single play even though I watched videos in 2x 😄.
Well Explained.
Thanks for the graph series.
Please make series on other topics too.
You're very welcome!
@@takeUforward Bro! Do you post extra videos when we join your channel or is it the same as if we only subscribe?
@@samkr200 it's same
Please bring tree series too, will remain thankful throughout my life.🙏
i can feel you dude
It is there 😉
@@striver_79 thankyou sir
@@AbhaySharma52194 pranam kijiye abhi ABHI
I believe in the Union function you could keep track of number of connected components…increment it if parent of u not equal to parent of v…if u and v same keep connected components same
path compression looks so simple in recursion, that's the beauty of recursion.
recursion is sasta while loop..beauty lol
@@pulkitprajapat7862 hahah
@@pulkitprajapat7862 backtracking kro for loop se phir
Referred to a many resources on the net but could conveniently understand the concept only from your video. Thank you so much for your efforts
You should have put a check in union that if(u != v) then only proceed for union otherwise it will do union for two nodes having same parent and will unnecessarily increase rank of one node
yrr ye banda kitna awesome hai, awesome explanation bhaiya :)
Keep sharing jahan bhi possible ho paaye. :)
the tree series and this graph series have ended my fear of trees and graphs ds.
C++ Code :
//check if 2 nodes are belong to the same components or not
#include
using namespace std;
void makeSet(vector&parent, vector&rank)
{
int n=rank.size();
for(int i=0;i
I think the time duration of this video has reduced to 14 min and part from 4:50 sec about 5-6 min of explanation is missing
yesss........... rank wala part hi gayab hai
The rank might change during path compression and we have not implemented anything in the findPar function to account for that change. We might be making sub-optimal connections in the union function if the ranks are unreliable
Same doubt
I think the same
Refer Tech Dose video for this. His video will exactly clear your doubt. Striver's graph series is great, but in some concepts like this one, it is lacking intuition.
@@amanagarwal6897 Thanks
@@amanagarwal6897 even tech dose video on rank and path compression is not changing the rank during every path compression....you can find any article no one is changing the rank during path compression and the reason i got to know is changing rank would increase the time complexity !
16:02 what is the logic of attaching 1 to 4 if we have done the path compression, the height of both the components are same now????
i think the rank of the 1 will also be 2 coz 0 ---> 1 for the 2 node and 1--->2 for 3 node and another doubt is that the path compression will happens when it will be called like in this case union (*, 7) for the second time then only it will be effective but for the first time it will tranverse for logn times
I literally understood this concept in a 24 minute video :0
Your explanation is neat
Please reUpload this video some part is missing around 4:50 @striver
Very well explained. The Rank and Path Compression is always very confusing, but this made it easy to remember and implement whenever required
hattimare
the best series for graph that i have come across till now
Sir, have you made videos on heaps and priority queue also?If no,can you please make it sir. It"ll be very helpful.All your contents helps a lot. Thanks!
Recursion is beauty, perfect example of recursion importance
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ?
What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
Just to reiterate the use of path compression. Is someone is still confused with the optimization-
at 14:00 secs- using the same example-
last query union (3,7)
x= findParent(7); // 7->6->4->4->4 so finally parent is 4 after 4 hops
y=findParent(3); // 3->1->1 parent 1
lets say we dn t do path compression we keep the parent array as it is in this step.
Now the next step is UNION which says -
lets suppose rank of x > rank of y
parent[y]=x; rank of 4 is greater than rank of 1
that means parent[1]=4
now lets say we have another query (something,7)
x= findParent(7); // 7->6->4->4->4 again we will have to make 4 hops
if we would have done path compression then
x= findParent(7); // 7->4->4 2 hops only.
instead of calling the vector rank , u can name it as height , it helps in much better understanding
why do we need height or rank if we are path compressing ?? Ultimately when we find parent for any node with path compression implemented, it will go at most one level to find absolute parent of the component, right ?
What I believe is if we are path compressing then we do not need rank to make algo efficient. Please explain if I am wrong.
When we compress the path,it can also change the rank of any node. Will this impact the logic or time complexity of the algorithm, since we are not handling this change in rank by path compression in our algo??
Simply Awesome !! I dont think I need any other video to understand this now.
Really very helpful ... Crystal Clear!!
for explaining path compression if some array example is used it would have more intuitive. Rest other part of video is super awesome.
You people are giving back to community. Good job🙌
Btw any mrwwe fan here 😁
You explained so beautifully by live coding !!!
why can't we compare parent[2] != parent[3] directly ? since after union operation parent array will contain compressed path only??
No it won’t, may be 3 had a tree. And you connected it to 2, so something below 3 has not been compressed yet.
Matlab kyahi padhaye ho striver bhai .... No one can teach better then you...🔥🔥🔥🔥🔥
Best explanation , I really wish this channel grow well, thank u striver .
Great video mate. I just totally visualised the theory explanation with the code. Fabulous!!!
great explaination brother.......tbh nobody explained it this good along with the code
bhaiya graph series se concept boht acche ho gye, ab ek list of ques aur de do jisse tagdi wali practice ho jaye sare graph algos ki.
In the union operation if the parents are the same then we can just skip it right, rather than entering the else statement and increasing rank[u] by 1 like your code does?
Actually the union is called only if parents are not same, look at the kruskal
@@takeUforward Alright thanks!
Understood! Super extreme explanation as always, thank you very much!!
Dont you need to update rank after path compression ? as the level of the tree will be decreased
I too have this question . Can someone answer?
shouldn't the time complexity be o(logn) with path compression and union, why does it become constant time?
So simple you made it!
Beautifully explained...Thanks Striver!!!
I almost shouted after I understood how the path compression is done
You're a blessing
22:45 If we are using path compression, can we not use parent array directly at line 48???
thanks a lot vaeya ...this is literally very very helpful....
path compression ke time rank bhi update karni padegi na
I think at 5:05 some part of video is missing
Superb Striver "Understood"
I referred some other sources and TC there was E Log E + E log V. why so and which is correct?
sir should we practice questions while watching videos or should we complete the playlist first and then attempt the questions
watch full palylist then attempt ques.
I LOVE THIS !!!!!!!!!!! whataaaaaaaaaaaaaaaa a playlist !!!!!!!!!!!!!😊😊
Well explained as expected striver bhaiya, please bring other series too.
It will be very helpful.
Thank You.❤️
bahut acchay say clear hogaya .
why do we not decreasing the rank when we compress the path as height of the tree is reduced.
Please make a series on dp!!
Is this 14 minute video complete?
Bro! Do you post extra videos when we join your channel or is it the same as if we only subscribe?
Its the same. Its just for appreciation purpose, nothing else :)
Thank You for Such a Wonderful Explanation
Something happened with the video, its incomplete. It was fine few days ago.
Ek level up whaaa bhaiya kya explain kiya 🥳🥳🥳🥳pr bhaiya 4 alpha kya h ye
Thank you!
Why no visualize parent array
hey striver...can we do path compression if we implement findparent function with while loop....?
I think not... because inorder to do path compression we need to have some sort of backtracking...which is not available in the iterative version of the function!!!
why we are not checking for decreasing the rank in path compression ???
You rock! I hope god blesses you abundantly!
Exceptional Explanation!
you have told nothing about the rank array which you have used , please explain it..
can we use it for directed graph?
MindBlowing Explanation bro
Thank you so much
in this que can we add a condition in the union func that if(u!=v)? jisse same parent waale pe union find nahi karega yeh please confirm
Nice explanation sir.. thanks for the playlist
bhaiya for the challenge we have to send only one screenshot after we do all the challenge videos ?
and the hashtag is to be used in linkedin while sending u the screenshot? or we can send it personally to your linkedin dm???
Suppose we have 4 vertices and their values: 55, 65, 22, 32.
Now, we created a parent array of size 10^5. Cool. Because every vertex gets themselves assigned as their parent initially (i.e. index value will be same as the vertex value.)
But, inside the makeSet() function, we're running the self-initialization loop for the COUNT of vertices i.e. 4 and not FOR THE vertices' value.
Eg. In the parent array, we're initializing index 0, 1, 2, and 3 with the same value as the index i.e. 0, 1, 2, 3. BUT, our vertices are actually present at index 55, 65, 22 and 32 respectively which do not get initialized as we only ran the loop for the COUNT of vertices i.e. 4.
So, shouldn't we run the makeSet() loop for all 10^5 elements. And, doesn't this brings a disadvantage of array space being wasted? :/
@take U forward
Disjoint set is Taserface of DSA
How does the rank work if they are all set to 0? What is updating the rank?
Watch the new video
what does alpha denotes in Time complexity: 4 x alpha ?
A small constant near to 1
@@takeUforward Okay, Thanks!
What exacty does rank array signify?
Python Code:
n=8
parent=[[]]*n
rank=[[]]*n
def makeSet():
for i in range(1,n):
parent[i]=i
rank[i]=0
def findpath(node):
if node == parent[node]:
return node
parent[node] = findpath(parent[node])
return parent[node]
def union(u,v):
u=findpath(u)
v=findpath(v)
if rank[u]
WHEN WE ARE DOING COMPRESSION THEN RANK OF PARENT NODE WILL DECREASE?
Nah let it be, no need to decrease.. as a particular node is getting decreased. There might be other nodes as we
What is this weird logic where the heights won't increase ? Can anyone explain ? The size of the tree after unite operation would increase, obviously!
very nice explanantion thank you bhaiya
I love the way you explain 🔥❤️
if i give u & v with same parent in union operation then the rank of their parent increases according to the union function written in the above code but no component was added, this should be an error.
please make it clear to me if possible
superb explaination
Great Explanation.
hey striver, in the makeSet() you wrote i
I just wrote snippet, you can declare globally or pss by parameter
@@takeUforward Ok. Thanks bro.
Next level explanation 💯💥💥
chaa gye guru ..thoko video pr like
Well,rank doesn't change in path compression?
Nah, rank does not guarantees to give you the height, but it will assure you to give the heavier tree of both.
Concept katai...killed Dead Slaughtered 😎😎
Kuvh jyada hi maas pasand hai😀😁
@@pasitopasito1967 haa 😂
Got it in a single watch😀
What is n in makeSet() ?
Hi Raj, in union operation, instead of parent[u] = v, can we do parent[u] = findPar(v)?
after entering the function, the first 2 lines are used to make u as the parent of u and v as the parent of v,
see u=findPar(u)
v=findPar(v)
so even if you write parent[u] = findPar(v), it won't change anything except calling the findPar() function once more and returning V itself
@@debottammazumder9103 Thank you Mazumder!!
i don't understand why rank is necessary since we are doing path compression at the end all the parents should have only one rank
No.. ranks are needed.. as bada tree chote me add hga, th bade trees k nodes fir path compress krne me time lengy na
@@takeUforward yes , I got it thanks
anyone knows which sublime theme he's using?
Can someone please clear my dount that in second last main, if statement if(findPar(2)!=findPar(3)) why cant we just check the parent array instead,i mean it do stores the parent right
No.. we always need the root of the tree.
Thanks for reply big fan of ur work
You are awesome💯