# Does this "reference" problem have a name?

I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course). The situation is as follows: I receive distinct items (A...E in the below sketch) one after the other. Each item has a relation which can generally be termed "descendance" or "family" and is in itself anonymous - the only requirement is that an item can only belong to one family and that it must somehow be possible to distinguish the families. Items keep coming in and are referenced to their own family (like A and B in step 1), but sometimes an item can change the situation for other items already received: see the second step of the sketch: a connection in C points back to A and B and revokes their original descendances and points them to the family of C. Such connections are transitive, which can be seen in step 3: the connection between E and C also converts the descendance of A and B to the new family of E.

The task I need to solve is to keep the descendance relation correct for all items. It may look trivial but the solution that I am looking for should be O(n), n == number of items. Is there a name (and most likely a different description) of the problem in literature?

• This sounds like the "disjoint set" or "union find" data structure. Sep 14 '18 at 15:05

## 1 Answer

This is disjoint-set data structure.

Here is the summary at Wikipedia. I put the statement about time-complexity in bold font to emphasize its efficiency.

In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

There are many tutorials for this data structures on the web, such as the one at TopCoder and the one at GeeksforGeeks.

• Well, I took O(n) for handling the whole number of n elements. I implemented path compression and believed in my intuition that it will yield O(1) for subsequent find operations but obviously the problem isn't so simple and I was just lucky. I am using it for finding connected sets of pixels in a binary bitmap. As I am currently only aiming for a sequential implementation, my case doesn't need union. Sep 15 '18 at 7:54