Disjoint Set | UNION and FIND

Рет қаралды 110,228

4 жыл бұрын

This video explains the basics of disjoint set data structure from scratch.I have explained all about disjoint set data structure in a simple and easy way to clear your basic understanding on the disjoint set data structure.I have taken intuitive examples and an intuitive algorithm to explain this data structure.I have explained the parent child relationship in a disjoint set by using tree structure for better understanding.I have explained the CODE implementation in the description below.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...

Пікірлер: 266

@AkashPawar-qv4ps 2 жыл бұрын

literally this is one of the clear and conceptual explanation of union find I have ever came across.

@yooos3 3 жыл бұрын

Clear and concise! It's funny the moment I saw how you created the array, I understood and I was able to code it as well! This video helped me clearly visualize how Union and Find works! Thank you!

@techdose4u 3 жыл бұрын

😂

@safalyaghoshroy2405 4 жыл бұрын

Pls don't discontinue graph series🙏🙏🙏

@smmahadibhuiyan4437 Жыл бұрын

this channel, this video is BEST. this topic is perfectly descrived here. None of video on this topic is not good as it in KZfaq . So RECOMMENDED for ALL.

@techdose4u Жыл бұрын

Thanks for your appreciation

@rummanchowdhury3807 Жыл бұрын

Fantastic explanation! It's great to hear you explain your thought process as you unfold the steps one by one

@sakshigupta7616 3 жыл бұрын

Awesome explanations! I am literally heading to your explanation for every topic I learn now and then! Keep goin'

@techdose4u 3 жыл бұрын

Thanks :)

@MilindGupta 2 жыл бұрын

Man you explained this so beautifully felt it's so easy now 😭🙏

@tranvuong3273 5 ай бұрын

it is very helpful. I hope this channel would have more people to watch because it deserves it. thanks a lot!

@naman_goyal 4 жыл бұрын

sir ur video content is very good.. in every competition i always say a time..han ye to techdose sir ki video mein dekha tha yaha yahi concept legega..thanku for this awesome concept

@techdose4u 4 жыл бұрын

Thanks bro....it means a lot :)

@PradeepKumarIIITD 3 жыл бұрын

I like video first, then start watching it... :)

@techdose4u 3 жыл бұрын

❤️

@ashwinram9081 4 жыл бұрын

Thanks for making this graph series. Your are always inspired to learn

@techdose4u 4 жыл бұрын

Welcome :)

@jewelchowdhury9752 Жыл бұрын

That is a great explanation of DSU..... I am deeply appreciative of your efforts and wanted to extend a heartfelt thank you.

@adityaojha2701 2 жыл бұрын

I am following this channel since it was having 30K subscriber. You have helped me a lot understanding DSA. Thanks a lot for such great explanations.

@techdose4u 2 жыл бұрын

Great ❤️

@manojg4451 3 жыл бұрын

Finally, a tutorial that makes sense 🙏🙏🙏

@techdose4u 3 жыл бұрын

Thanks :)

@shaswatdas6553 3 жыл бұрын

a few months left before the channel explodes, cuz the content is top notch!

@techdose4u 3 жыл бұрын

Thanks for appreciation :)

@shaswatdas6553 3 жыл бұрын

i commented on cycle detection in directed graph. Can you clear the doubt? code-gist.github.com/SuryaPratapK/e84cf8624da8a690f11d5ce31745b808 video-kzfaq.info/get/bejne/Zsp6oLemsti5ioE.html comment- Sir in this function need correction i guess... bool isCyclic_util(vector adj[], vector visited, int curr) { if(visited[curr]==true) return true; visited[curr] = true; bool FLAG = false; for(int i=0;i

@princeakhil208 4 жыл бұрын

Tech dose is back 😁 maza aa gaya

@techdose4u 4 жыл бұрын

Yep :D

@rajatbudania6181 4 жыл бұрын

Brilliant as usual :) Sir, can u plz make videos on OS or DBMS totally focusing placements!! Will be a huge help :)

@techdose4u 4 жыл бұрын

I will give the important topics to study soon for theory preparation.

@bhuvanchandrajoshi9138 3 жыл бұрын

I think you are underrated like imdb movies

@techdose4u 3 жыл бұрын

Hope I get good reach soon :)

@iamakifislam 3 жыл бұрын

Your tutorial is the best in the internet. ❤️

@techdose4u 3 жыл бұрын

Thanks :)

@mdimranhosen6674 2 жыл бұрын

Brilliant as usual.

@debaratighatak2211 3 жыл бұрын

Thank you so much sir for giving such an amazing explanation❤️🙏

@techdose4u 3 жыл бұрын

Welcome :)

@mainakmondal8691 3 жыл бұрын

Can't be better explanation than this one..thank you sir.

@techdose4u 3 жыл бұрын

Welcome :)

@K_EC_AushoRoup 3 жыл бұрын

Thanks!! It helped. I was struggling a lot in this topic.

@techdose4u 3 жыл бұрын

Welcome

@shyammakwana3770 3 жыл бұрын

Sir again very very deeply respect to you and your all Playlist on diff topics it is very useful for us. Never stop to make videos 🙏🙏🙏🙏🙏

@techdose4u 3 жыл бұрын

Thanks :)

@SUJOYPAULJOBS 3 жыл бұрын

khub bhalo bojalen sir nice teacher

@techdose4u 3 жыл бұрын

Dhonnobaad :)

@beingvoid3246 2 жыл бұрын

i have a doubt , at 26:06 , we have already found the absolute parent of x,y so why are we again finding the absolute parent of Fromp and Top as we already did it in the iscyclic function ?

@LUKFUNTV 2 жыл бұрын

Redundancy may happen sometimes.... Just ignore those 2 lines.. As we have already found the parents..

@namansharma5128 2 жыл бұрын

was finding this doubt only 😅😅

@sudhanshukumar1558 4 жыл бұрын

I got my binge watching content. Thanks 😊

@techdose4u 4 жыл бұрын

Awesome :D

@sudhanshukumar1558 4 жыл бұрын

@@techdose4u done with watching it, great explanation 👍

@techdose4u 4 жыл бұрын

Thanks

@MJ-ur9tc 3 жыл бұрын

Superb. Very detailed explanation. Please keep up the good work. It made me subscribe to your channel. Now, I’ll definitely watch all of your videos. Thanks a ton for the excellent content.

@techdose4u 3 жыл бұрын

Welcome

@jameskennedy674 2 жыл бұрын

Pretty good Explanation.

@jayantaghosh7678 3 ай бұрын

awesome explanation

@deepakprajapati5064 3 жыл бұрын

Explaining complex problem in a simple way 🔥🔥

@techdose4u 3 жыл бұрын

Thanks :)

@sallaklamhayyen9876 Ай бұрын

great explanation thank you so much🥰🥰🥰

@yulianloaiza Жыл бұрын

You explain so well! Thank you very much :)

@techdose4u Жыл бұрын

Welcome :)

@anmoljain5910 4 жыл бұрын

seen many videos on this topic. This one explains the concept best. Please make Union by rank and Path Compression video soon.

@techdose4u 4 жыл бұрын

Yes

@amrkhalid275 6 ай бұрын

thank u sir very helpful ...

@jigarsingh600 4 жыл бұрын

Very well explained. Please keep making such informative videos.

@techdose4u 4 жыл бұрын

Thanks

@PoojaGupta-ry3oj 3 жыл бұрын

can you also make video on backtracking..till now I haven't found any good resource for it. ur videos are so good.. it gives grasp on the concept in one go..

@techdose4u 3 жыл бұрын

I will start that series later along with dynamic programming.

@PoojaGupta-ry3oj 3 жыл бұрын

@@techdose4u thank u.. wish to see soon :)

@Faiazur_Rahman_Bhuiya_- 3 жыл бұрын

I love this guy.

@ss-xh3hf 3 жыл бұрын

Loving it please make a similar series on backtracking

@techdose4u 3 жыл бұрын

It will come. Stay tuned :)

@impatientgaming9868 6 ай бұрын

Really Helpful!

@divyanshdixit4944 4 жыл бұрын

Thanks for the amazing video. Please add Linux video that you promised, whenever you get time. Once again keep up the good work.

@techdose4u 4 жыл бұрын

Linux video for theory syllabus?

@divyanshdixit4944 4 жыл бұрын

@@techdose4u Yes sir, list of important topics and commands of Linux for interview

@acousticIndie 3 жыл бұрын

Thank you so much, means a lot! Keep it up!

@techdose4u 3 жыл бұрын

Welcome :)

@frunked 3 жыл бұрын

helped me on my exam. much love from university of illinois 👍

@techdose4u 3 жыл бұрын

Thanks Matt ❤️

@joydeepbhattacharjee5305 3 жыл бұрын

great video...best channel for DSA

@techdose4u 3 жыл бұрын

Thanks :)

@prajwalmp8583 3 жыл бұрын

This gave me a clear picture... thanks a lot😀

@techdose4u 3 жыл бұрын

Welcome

@kumartejaswi712 3 жыл бұрын

bhai yaar😍

@lancelotdsouza4705 2 жыл бұрын

beautifully explained

@uditghosh3247 4 жыл бұрын

This is pure gold.

@techdose4u 4 жыл бұрын

Thanks

@aayush5474 3 жыл бұрын

Best explanation bro! Thank you

@techdose4u 3 жыл бұрын

Welcome :)

@shubhamkhurana7545 4 жыл бұрын

That was really something new!!

@techdose4u 4 жыл бұрын

@ridoychandradey8337 Жыл бұрын

Thank you very much.

@nishithramanuj509 2 жыл бұрын

Very good explanation sir

@techdose4u 2 жыл бұрын

Thanks 😊

@shagunlamba6481 3 жыл бұрын

amazing explaination, thank you :)

@techdose4u 3 жыл бұрын

Welcome :)

@kunalsoni7681 4 жыл бұрын

Very helpful video 😊😇.. Thank you sir

@techdose4u 4 жыл бұрын

Welcome :)

@rajmani4486 3 жыл бұрын

amazing explanation...

@techdose4u 3 жыл бұрын

Thanks :)

@VarunKaushal-zx9zq Жыл бұрын

Amazing sir

@sarthakbhatia7888 3 жыл бұрын

Thankyou..:)...This series is great

@techdose4u 3 жыл бұрын

Thanks

@abhishekkeer1520 4 жыл бұрын

what is need of again call find function in union_op because we already get absolute root of both element ?

@shushantgaur9420 3 жыл бұрын

Exactly... Line 15 and 16 are doing same thing as line 24 25, right?

@techdose4u 3 жыл бұрын

You can skip that. I have commented it in the next video.

@shushantgaur9420 3 жыл бұрын

@@techdose4u yes I saw that afterwards but I forgot to remove this comment😅. By the way that's one hell of an explaination..... I don't think I'm gonna forget it anytime soon.... Thanks 😊.

@techdose4u 3 жыл бұрын

@@shushantgaur9420 You better not forget it :P

@shushantgaur9420 3 жыл бұрын

@@techdose4u never😁

@musheer.ahmed.0 2 жыл бұрын

Thanks you very much😁

@khaledov7305 2 ай бұрын

Thanks a lot .

@bespoyasov 2 жыл бұрын

Awesome! Thank you!

@techdose4u 2 жыл бұрын

Welcome 😊

@kavishamanchanda7141 3 жыл бұрын

Can you please tell me in the union function why did you add absolute parents in the dfus array and why not the original fromP and toP

@siddharthasharma9316 4 жыл бұрын

Going to watch this tonight.....pakka

@techdose4u 4 жыл бұрын

Nice

@prabhatchanchal 4 жыл бұрын

Thanks sir. please make all of DSU lecture in series from now. like kruskal and DSU on grid.

@techdose4u 4 жыл бұрын

I will give optimized approach explanations and later I will add more complex algos. Fir now, target is to cover for interview.

@Leetforces_com 4 жыл бұрын

Wow!! too easy explanation ❤️

@techdose4u 4 жыл бұрын

Thanks

@Mandeepsingh-jo5cf 3 жыл бұрын

Thanks graph specialist.

@techdose4u 3 жыл бұрын

Welcome :)

@VarsneyaSrinivas 3 жыл бұрын

Pls don't ever stop.

@techdose4u 3 жыл бұрын

Sure :)

@dochimekashiariri7610 2 жыл бұрын

in the union function, there is no need to write the find function right?? cause we are already sending the absolute parent to it.

@dharmeshupadhyay4778 3 жыл бұрын

sir i love your videos , you are an excellent teacher , and sir your voice is fabulous sir plz also make MOTIVETIONAL VIDEOS ,i will be first to watch it sir i thing in union() operation their is no need to call find() bcz we already have parents ,?????????????????????

@techdose4u 3 жыл бұрын

Try it out. Maybe it's true :)

@shanmukhavarma3361 4 жыл бұрын

Tq bro I could solve dsu problems in codeforces

@techdose4u 4 жыл бұрын

Nice :) this was just basic. I will soon make optimized dsu as well :)

@shreelakshmi6890 3 жыл бұрын

Great video again!!👌

@techdose4u 3 жыл бұрын

Thanks :)

@frankdaniel3506 2 жыл бұрын

Which Software are you using for explanation?Thanks-Frank

@karthikeyank7467 Жыл бұрын

Thank you buddy

@rudreshajgaonkar 2 жыл бұрын

If the nodes are 0,1,2,3 then using a Array is fine to keep track of parent child relationship. But the moment we have vertices as 3,4,5,6 isnt it good to keep a map in that place?

@sagarlandge3271 3 жыл бұрын

Best 26.42 minutes of my life

@yasharma2301 3 жыл бұрын

Perfect explanation!

@techdose4u 3 жыл бұрын

Thanks :)

@ayushgoel9584 4 жыл бұрын

Hi bro, I checked your content , it is awesome, but it would be great if you can arrange all your videos in difficulty level and topic wise level in your playlist.Many videos are missing in playlist or repeating in playlist. Please try to create proper sequence of all your videos, so that it would be helpful for everyone

@techdose4u 4 жыл бұрын

Thanks. I am trying to do that

@ayushgoel9584 4 жыл бұрын

@@techdose4u yeah, I have recommended your channel to many of my friends, some of them are begineers, and they get lost from where to start watching your videos, thats why

@techdose4u 4 жыл бұрын

Okay....I understand. I will arrange them. Actually I haven't covered many basic topics like time and space complexity, hash, heap etc properly. There are missing topics as well. So, as soon as I finish graph algorithms, I will cover the basics and clear them so that I will have everything required for placement purpose :)

@rishijha9860 4 жыл бұрын

Very well explained!!!

@techdose4u 4 жыл бұрын

Thanks :)

@yihongliu3850 3 жыл бұрын

very nice content as usual sir! just have one small question -- at line 24& line 25, we already find the absolute parent of the subset.. and in the union_op function (line 13-18) we find that again.. is it because we want to keep the complete functionality of union_op here?

@techdose4u 3 жыл бұрын

I think you can skip that. I may have forgot to not comment those lines

@yihongliu3850 3 жыл бұрын

@@techdose4u haha thanks!!

@mahipalsingh-yo4jt 3 жыл бұрын

great explanation sir !!!!!!!!!!!!!!!!!!!!

@techdose4u 3 жыл бұрын

Thanks

@pulkitmoolchandani6049 4 жыл бұрын

great video :)

@techdose4u 4 жыл бұрын

Thanks :)

@acxd 3 жыл бұрын

Amazing amazing !!

@techdose4u 3 жыл бұрын

Thanks thanks :D

@AltafHussain-on2oe 3 жыл бұрын

Thanks from the Heart 💖

@techdose4u 3 жыл бұрын

Welcome 😊

@mathewsjose1990 10 күн бұрын

Nice explanation!

@techdose4u 7 күн бұрын

thanks

@himanshuchhikara4918 4 жыл бұрын

Welcome back sir

@techdose4u 4 жыл бұрын

Thanks :)

@Aman-jc7pu 2 жыл бұрын

I think there is no need to again find the absolute parent in union function. By the way Great Explanation.

@vishaltk3013 3 жыл бұрын

which software are you using to draw and demo using the slides?

@nehamahendrasingh4478 4 жыл бұрын

Hi :)Thank you so much for the video .. Could you please make a video on time and space complexity .Thank you

@techdose4u 4 жыл бұрын

Do you mean time and space complexity series videos?

@nehamahendrasingh4478 4 жыл бұрын

TECH DOSE yes please, Atleast one video explaining how to calculate time and space complexity

@niteshkhetan9757 3 жыл бұрын

Sir in the first tree which looks like linked list, why is 2 the parent of 3, instead 3 is the parent of 2... Right? Am I missing something?

@shalini-j-2r 3 жыл бұрын

I do not think , we need to use find again in union method as we have already find the parent of both elements. Is there any specific reason?

@techdose4u 3 жыл бұрын

No specific reason. Try to exclude it. I had exluded it in my next lecture.

@dhanichauhan3010 3 жыл бұрын

sir very nice speaking skills

@techdose4u 3 жыл бұрын

Thanks :)

@nikitamandlik6067 2 жыл бұрын

Thanks for the explanation :) May I know which tool is used for explaining the problems

@david.breyer 2 жыл бұрын

Sir, why does 17:35 connect 0 to 3 in the image but the array is 1 to 3 ? It should be like: 0 -- 1 / ｜ 3 -- 2

@amitavamozumder73 3 жыл бұрын

end cycle detection was basically Kruskal's algorithm!

@emilybao 2 жыл бұрын

Thank you!

@techdose4u 2 жыл бұрын

Welcome 😊

@mdzama1012 Жыл бұрын

There is a small BUG in union( ) function: void Union(int val1, int val2) { int absRoot1 = Find(val1); int absRoot2 = Find(val2); if (absRoot1 != absRoot2) // this check needs to be added parent[absRoot1] = absRoot2; } because imagine val1 and val2 belongs to the same set

@suryakiran2970 Жыл бұрын

Not required, if both are equal then it will adds to it parent only

@AkshayKumar-xh2ob 3 жыл бұрын

Kabhi college me ratta mara tha iska code, aaj usage samajh aaya😅

@Sky-nt1hy 3 жыл бұрын

Hi !! I have a question regarding the code. Aren't line 15,16 unnecessary? Since when you pass fromP and toP to union_op function, they're already the absolute roots so it seems there's no need to find the absolute roots when they are already. Thank you!

@techdose4u 3 жыл бұрын

Yea seems so. You can comment that.

@Sky-nt1hy 3 жыл бұрын

@@techdose4u That was almost an instantaneous reply. Thank you!

@techdose4u 3 жыл бұрын

Welcome :)