## A Union-Find Algorithm

The first implementation of an algorithm for solving the dynamic connectivity problem, called Quick-find.

It is also called as eager algorithm, for solving kind activity problem.

The data structure that we’re going to use to support the algorithm is simply an integer array indexed by object.

P and Q are connected if they have the same entries the array.

So there are two key steps in this:

- Find: Check if p and q have same id

2. Union: To merge components containing p and q, change all entries

whose id equals id[p] to id[q].

Lets take the following example for a better understanding.

To get the connections between the given objects in the above picture,

First, we must form connections with the objects themselves .i.e. assign them as their own ids. by initially, setting up the ID array, with each entry, equal to its index.

Next, we give various commands to form the connections.

- Union(4,
**3**) : We’re going to change, all entries, whose**first ID**to the**second**one. So in this case, we’ll change the, connect three and four means that we need to change the**four**to a**three**.

2. Union(3,**8**) : Both(refer to the above step) of those entries have to change to eight.

3. Union(6,**5**) : Again, we change the first one to match the second one. So to connect six and five, we change the six to a five.

4. Union(9,**4**) and Union(2,**1**)

5. If the user inputs connected(8,**9**) then function returns true (already connected through 3 and 4) and on inputting connected(5,0) it returns false.

6. Union(5,**0**), Union(7,**2**) and Union(6,**1**)

## Implementation of the algorithm

We first create a public class and declare our data structure array, int id.

Create a constructor and two functions:

- QuickFindUF Constructor: To assign each object with its own id using a for loop
- connected() Function : Returns true or false based on p and q connectivity
- union(): To change id[p] to id[q] .i.e. second id to first as we did in the above example.

Quick-Find algorithm is quick, although to check array entries a constant number of times, is problematic making the union operation too expensive and less efficient.