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? enter image description here

  • 1
    This sounds like the "disjoint set" or "union find" data structure. – Dan Doel Sep 14 at 15:05
up vote 3 down vote accepted

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. – Vroomfondel Sep 15 at 7:54

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.