# 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, 2018 at 15:05

• 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, 2018 at 7:54