The efficiency of an algorithm sometimes depends on the data structure that is used. An efficient data structure, like the disjoint-set-union, can reduce the execution time of an algorithm.

Assume that you have a set of N elements that are into further subsets and you have to track the connectivity of each element in a specific subset or connectivity of subsets with each other. You can use the union-find algorithm (disjoint set union) to achieve this.

Let%u2019s say there are 5 people A, B, C, D, and E.

A is B's friend, B is C's friend, and D is E's friend, therefore, the following is true:

- A, B, and C are connected to each other
- D and E are connected to each other

You can use the union-find data structure to check each friend is connected to the other directly or indirectly. You can also determine the two different disconnected subsets. Here, 2 different subsets are {A, B, C} and {D, E}.

You have to perform two operations:

- Union(A, B): Connect two elements A and B
- Find(A, B): Find whether the two elements A and B are connected

Example You have a set of elements S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Here there are 10 elements (N = 10). Use an array *arr* to manage the connectivity of the elements. Arr[ ] that is indexed by elements of sets, which are of size N (as N elements in set), can be used to manage the operations of *union* and *find*.

Assumption

A and B objects are connected only if arr[ A ] = arr[ B ].

Implementation

To implement the operations of union and find, do the following:

- Find(A, B): Check whether arr[ A ] = arr[ B ]
- Union(A, B): Connect A to B and merge the components that comprise A and B by replacing elements that have a value of arr[ A ] with the value of arr[ B ].

Initially there are 10 subsets and each subset has one element in it.

When each subset contains only one element, the array *arr* is as follows:

Let%u2019s perform some operations.

- Union(2, 1)

The *arr* is as follows:

Union(4, 3)

Union(8, 4)

Union(9, 3)

The *arr* is as follows:

- Union(6, 5)

The *arr* is as follows:

After performing some operations of Union (A ,B), there are now 5 subsets as follows:

- First subset comprises the elements {3, 4, 8, 9}
- Second subset comprises the elements {1, 2}
- Third subset comprises the elements {5, 6}
- Fourth subset comprises the elements {0}
- Fifth subset comprises the elements {7}

The elements of a subset, which are connected to each other directly or indirectly, can be considered as the nodes of a graph. Therefore, all these subsets are called *connected components*.

The union-find data structure is useful in graphs for performing various operations like connecting nodes, finding connected components etc.

Let%u2019s perform some find(A, B) operations.

- Find(0, 7): 0 and 7 are disconnected, and therefore, you will get a false result
- Find(8, 9): Although 8 and 9 are not connected directly, there is a path that connects both the elements, and therefore, you will get a true result

When these operations are viewed in terms of components, then:

- Union(A, B): Replace components that comprise the two objects A and B with their union
- Find(A, B): Check whether the two objects A and B are in the same component

If you perform the operation union(5, 2) on the components mentioned above, then it will be as follows:

The *arr* is as follows:

Implementation

*Approach A*

Initially there are N subsets containing one element in each subset. Therefore, to initialize the array use the initialize () function.

```
void initialize( int Arr[ ], int N)
{
for(int i = 0;i<N;i++)
Arr[ i ] = i ;
}
//returns true if A and B are connected, else returns false
bool find( int Arr[ ], int A, int B)
{
if(Arr[ A ] == Arr[ B ])
return true;
else
return false;
}
//change all entries from arr[ A ] to arr[ B ].
void union(int Arr[ ], int N, int A, int B)
{
int TEMP = Arr[ A ];
for(int i = 0; i < N;i++)
{
if(Arr[ i ] == TEMP)
Arr[ i ] = Arr[ B ];
}
}
```

Time complexity (of this approach)

As the loop in the union function iterates through all the N elements for connecting two elements, performing this operation on N objects will take O(N^{2}) time, which is quite inefficient.

Implementation Code:

#include<iostream>

using namespace std;

void initialize( int Arr[ ], int N)

{

for(int i = 0;i<N;i++)

Arr[ i ] = i ;

}

//returns true if A and B are connected, else returns false

bool find( int Arr[ ], int A, int B)

{

if(Arr[ A ] == Arr[ B ])

return true;

else

return false;

}

//change all entries from arr[ A ] to arr[ B ].

void unionr(int Arr[ ], int N, int A, int B)

{

int TEMP = Arr[ A ];

for(int i = 0; i < N;i++)

{

if(Arr[ i ] == TEMP)

Arr[ i ] = Arr[ B ];

}

}

int main(){

int a[11],n=10;

initialize(a,n);

cout<<"Printing array entries:\n";

for(int i=0;i<n;i++){

cout<<a[i]<<" ";

}

cout<<endl;

cout<<"Checking whether 2 and 3 belongs to same array:\n";

if(!find(a,2,3)){

cout<<"No";

}

else{

cout<<"Yes";

}

cout<<endl;

cout<<"Making 2 and 3 to be in same group\n";

unionr(a,n,2,3);

cout<<"Checking whether 2 and 3 belongs to same array:\n";

if(!find(a,2,3)){

cout<<"No";

}

else{

cout<<"Yes";

}

cout<<endl;

}

--------------------------------------------------

Output:

Printing array entries: 0 1 2 3 4 5 6 7 8 9 Checking whether 2 and 3 belongs to same array: No Making 2 and 3 to be in same group Checking whether 2 and 3 belongs to same array: Yes

## Comments