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:
[ Ссылка ]

Music: bensound.com

свернуть