Disjoint Set Data Structure - Union Find Tutorial

In this tutorial we will learn all about a data structure called Disjoint-Set. Sometimes it’s also referred to as Union-Find or Merge-Find Set.

This is a remarkably simple data structure yet it has the power to solve certain problems that are otherwise very difficult to deal with. To better understand its purpose, let’s consider the following problem:

Suppose you are implementing a new social network, similar to Facebook. There are users, each of which could be friends with some number of other users. In this illustration, lines connecting 2 users indicated that those two users are friends and thus form a group. When a user from one group makes a friend with a user from another group, then those two groups become connected and from that point on they are considered to have been merged into a single large group. Meaning, all of the users in that one large group are now friends with one another.

In more concrete terms, imagine that each user has an integer ID and you are given a list of integer pairs. Each integer pair indicates that those two particular users are friends.

When you have millions and millions of users, the challenge is to answer the following questions:

Given two user IDs, can you check if they are friends?
What is the size of the largest group of friends?

Alternate formulations of the same problem are used in coding interviews. Here are a couple of samples:

leetcode 547 "Number of Provinces":

hackerrank "Components in a graph":

Java implementation of Disjoint Set with Union Find operations:

More information on Ackermann function:

[yoshi]

Using the negative scale to store size is a great idea! Love your videos

[ravishankarprasad]

Your videos are best value for time. To the point, with all the necessary details and visuals making it easy to understand and visualize, and no rambling, and wastage of time in writing/typing.

[raydot]

Awesome! Been reading about this for two weeks now and this is the first time I've understood the point/purpose of a disjoint set.

[a..b]

Hi, your videos helped me a lot when I was looking for a job! I know it takes a lot of effort for these, just wanted to let you know we appreciate it! I think if you made videos every week or 2 you would explode, but understand you're probably busy with your full time commitments. Thanks

[cripz]

Loved the video!
Can you make one on the topic flows, cuts, bridges, articulation point, dfs tree?

[rajneeshverma]

one of the best explanation, precise and compact implementation 👍

[jean-lucsedits]

Better explanation then the first suggestion when searching "union find", thank you <3

[kevinsmirnov]

boah, ur videos burn through the matter. Pure delight. I hope u can keep the quality up.
Are u planning on doin a video on global alignment? Since u already covered the string matching it would fit (imo).

[adai]

Love your videos - the most intuitive ones I've ever watched. More please? :P

[aNeutrino]

Thank you for your effort on the algorithm video. I wanted to share that I found the background music quite distracting, to the point where it was impossible for me to focus on the content.

[sumeetagarwal]

thanks! I actually had this DS on my list to look up and learn

[astamurkirillin]

Great explanations, Andrey! Your channel is awesome!

[Vaaaaadim]

Neat. By delaying the update of the parent index for as long as possible, you can deduplicate work. Some values will have some parts of their paths compressed for free, provided that union operations are frequent enough. As well it's a very simple representation.

In a worst case scenario though, you could imagine that every time two sets are merged, every single element of the resulting set has the find operation performed on it. For this kind of input, it would be no better(asymptotically) than a naive solution. The naive solution that comes to mind for me is that you can have a hashmap which maps values to the id of the hashset they belong to, have a hashmap which maps set id's to hashsets, and the find and union implementation would be obvious. That being said, the data structure you present would have far less overhead in comparison to two hashmaps and many hashsets.

[ManojKumaryOyOmaDy]

You also given links for practice, thank you.

[madhukiranattivilli]

Hi Andrev,

What quality content u have‼‼‼

I'm ammmmazed‼‼‼

There are many yt channels with amazing DS ALGO content, but I guess u r having the best presentation -- graphics, animations, etc

I would love to know, if u r interested to share, how u make ur videos. May be u can make a video on this aspect. I will deeply appreciate.

And, please don't stop making videos on programming concepts (DS, ALGO, problem solving techniques). Please make millions of them.

I became ur fan. I'm gonna watch every videos of yours.

Cheers
Madhukiran

《btw, did I write ur name correctly❓ -- Andrev》

[y.violetguo]

can you make a video on the kernel mapping function? your animations are amazing!

[jeffwangvids]

great vid thanks learning this in class right now

[SauravSahu]

Your content and voice are always super cool. But addition of the music in this video is distracting. Could have avoided background sound. Thanks.

[ketanyadav]

How this can be implemented when node are dynamic and edges also can change for a node

[spyrowolf]

Thank you for the video!, Please try avoid using catchy music in the videos, it makes it hard to concentrate (if you have to use music please try use very subtle or barely noticeably)