**Union**: Connect two elements with each other.

**Find :**To Check two elements belongs to same subset or not.

**Lets see a example :**

Array | 0 | 1 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**UNION (A,B) :**Find all values in Array which are equal to value of Array [ A ] and replace all these values with value of Array [ B ].

**1. UNION (0,1) :**Here A = 0,B = 1. hold values at index 0 and 1 into variables tempA and tempB.

Array | 1 | 1 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**2. UNION (2,3) :**Here A = 2,B = 3. hold values at index 2 and 3 into variables tempA and tempB.

Array | 1 | 1 | 3 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**3. UNION (2,4) :**Here A = 2,B = 4. hold values at index 2 and 4 into variables tempA and tempB.

Array | 1 | 1 | 4 | 4 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**Diagram :**

**Code Snippet :**

**Time Complexity :**

**Second Approach :**

**Lets see a example :**

Array | 0 | 1 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**1. UNION (0,1) :**Here A = 0,B = 1. hold values at index 0 and 1 into variables rootA and rootB.

Array | 0 | 0 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**2. UNION (1,3) :**Here A = 1,B = 3. hold values at index 1 and 3 into variables rootA and rootB.

Array | 0 | 0 | 2 | 0 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**3. UNION (5,3) :**Here A = 5,B = 3. hold values at index 1 and 3 into variables rootA and rootB.

Array | 5 | 0 | 2 | 0 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

Let’s find root of 3 it will give you more understanding about root element.

**Note : By Using above approach we must ensure that it should not create a cycle otherwise finding a root element will stuck in infinity loop.**

**Diagram :**

**Code Snippet :**

**Time Complexity :**

**Third Approach :**

**Lets see a example :**

Array | 0 | 1 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

Size | 1 | 1 | 1 | 1 | 1 | 1 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**1. UNION (0,1) :**Here A = 0,B = 1. find the roots of both as explained in second approach.

Array | 0 | 0 | 2 | 3 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

Size | 2 | 0 | 1 | 1 | 1 | 1 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**2. UNION (1,3) :**Here A = 1,B = 3. find the roots of both as explained in second approach.

Array | 0 | 0 | 2 | 0 | 4 | 5 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

Size | 3 | 0 | 1 | 0 | 1 | 1 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**3. UNION (5,3) :**Here A = 5,B = 3. find the roots of both as explained in second approach.

Array | 0 | 0 | 2 | 0 | 4 | 0 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

Size | 4 | 0 | 1 | 0 | 1 | 0 |

Index | 0 | 1 | 2 | 3 | 4 | 5 |

**Diagram :**

**Code Snippet : **find operation and root operations is same as previous and we just modify union operation and init operation.

Above union operation balancing tree so it is also called **weighted-union operation.**

**Time Complexity : **Due to balancing tree above approach maintain time complexity to log_{2}N.

**Path Compression :**

In above all explanation when finding root to A, A pointing to it’s parent element.Now we will modify it such that A points to its grandparent.When this path compression is used with weighted-union operation, it will maintain time complexity to log*N which computes number of times finding logN before reaching N reaches to 1.

**Run a simple C program :**

**Output :**

**Size array**

**4 0 1 0 1 0**

**0 and 5 belongs to same subset**

**1 and 2 are belogns to different subset**

Size array tells us number of subsets and which subset has how many number of elements.

**Thanks**