The deal with Union Find data structure is that they are composed of sub-data structures. what I mean by that would be crystal clear after I present the big picture:

As you can see, our UnionFind is going to be made up from 2 arrays(say of size n, each) and a forest of up trees to communicate between them.

**NOTE:** the reason why both arrays are of size n is because when you are given n elements, you are obliged to keep them in an array of size n, on the other hand, each element is a set by itself until we unify(merge) it with another, thus, the maximum number of sets is n as well! So now you’re wondering:

## how does this beast work, anyway?

The principle is pretty straight forward:

- Each element in the array points to the corresponding node in the up-tree(i.e. the node which holds the data of the element)
- All the nodes in a particular up-tree refer to the same set.
- In order to know to which set a given element refer, we need to get to the node of that given element, and from there to “climb up” the up-tree until we reach the root.
- The root of the up-tree points to the corresponding set in the “sets” array on the left.

Sounds cheesy enough for you now? I bet it does, but it’s cool too right?!

# code

If you’re rather interested in the product itself than what it contains, please **click here** for the FULL generic implementation in C++

# API

Let’s dwell for a moment of the interface functions which this data structure support:

- makeSet: created a new set with one element
- union: given 2 elements(or 2 sets), unify them into one set
- find: given an element, find to which set it refers.

According to the sketch above, you already know that we want to find some way of implementing an up-tree! Like every tree in data structures, it’s made up from nodes!! Thus, we should create a node instance to construct the up-tree. So how we should do that? and what it should contain, eh? Here’s the answer:

### And in code:

/* This struct represents the atomic unit of the Union Find. * Basically, this struct contains info regarding a single element. * parameters: * @param data: the data which the element holds * @param size: number of elements this current node is their parent. * @param set: sequential number of the set to which this node * @param parent: pointer to the parent node of 'this' node.*/ template struct DisjointNode { T data; int set; DisjointNode* parent; DisjointNode(T Data); DisjointNode(int set1); DisjointNode(); ~DisjointNode(); };

Later comes the other atomic unit which represents a single set, or a department:

/* * Struct to represent one unit of a set of multiple elements * Typename of this struct is no longer 'T' as a set should contain * completely different type of information, * thus require another typename */ template struct Set { int size; D department; Set(); };

Now, I can present the Main class – `UnionFind`

which contains the API of the data structure:

/* * Main class. * Parameters: * @param : type of the elements. * @param : type of sets(departments) * @param n: size of the universe - number of elements in the system. * @param elements: array of disjoint nodes: * each cell has a pointer to the corresponding node in the up-tree. */ template class UnionFind { private: int n; int aux_find(DisjointNode* node); DisjointNode* getUpTreeRoot(int ele); DisjointNode* aux_getUpTreeRoot(DisjointNode* node); public: DisjointNode* elements; Set&amp;amp;lt;T, D&amp;amp;gt;* sets; /* API */ UnionFind(int N); ~UnionFind() { destroy(); } UnionResult unionSets(int ele1, int ele2); int find(int element); void destroy(); };

Considering the totally different lively colors present in the

tutorial hood and what they signify, some people’ are

confronted with the concern of which coloration corresponds to their sure diploma.

https://math-problem-solver.com/ . There are various shocking and

contradictory aspects to Erdos’s life.

LikeLike