**Disjoint Sets Introduction**

- A tree is used to represent each set and the root to name a set.
- Each node points upwards to its parent
- Two sets A and B are said to be disjoint if A – B = f. i.e., there is no common element in both A and B
- A collection of disjoint sets is called a disjoint set forest
- An array can be used to store parent of each element

Let **Σ **= { S1 , S2 , …, Sk } be a collection of dynamic disjoint-sets of the elements and let x and y be any two elements. We want to support:

**Make-Set(x): **create a set containing x

**Find(x): **return which set x belongs

**Union(x, y): **merge the sets containing x and containing y into one

**Example:**

n=11, 4 sets

s1 = {1*,*7*,*10*,*11} , s2 = {2*,*3*,*5*,*6}, s3 = {4*,*8} and s4 = {9}

**Disjoint set operations in daa**

Two important operations performed on disjoint sets are:

**Union****Find**

**Disjoint set operations Union**

- If S1 and S2 are two disjoint sets, their union S1 U S2 is a set of all elements x such that x is in either S1 or S2
- As the sets should be disjoint S1 U S2 replaces S1 and S2 which no longer exist
- Union is achieved by simply making one of the trees as a subtree of other i.e to set parent field of one of the roots of the trees to other root

**Disjoint Sets:**

**Set Representation:**

- An array can be used to store parent of each element
- The
**i**th element of this array represents the tree node that contains the element I and it gives the parent of that element - Root node has a parent -1
- An array P[1:n] can be taken for all n elements in the forest
- Element at the root node is taken as the name of the set

**Example: **n=11, 4 sets S1 = {1*, *7*, *10*, *11}, S2 = {2*, *3*, *5*, *6}, S3 = {4*, *8} and S4 = {9}

**UNION FIND Algorithms**

**Union:**

** ****Find:**

** **

In a worst-case scenario **SimpleUnion()** and **SimpleFind()** perform badly. Suppose we start with the single element sets **{1} ,{2},…,{n}** , then, execute the following sequence of unions and finds

**UNION(1**

FIND(1)

*,*2)*,*UNION(2*,*3)*,…,*UNION(n*–*1,n)*,*FIND(2)

*,…,*FIND(n)

*.*

This sequence results in a skewed tree

Time complexity for 1 union = **1**

Time complexity for n-1 union = **n-1**

Therefore Tall unions =** O(n)**

Time complexity for 1 find = **i**

Time complexity for n find = **1+2+….+ n-1 + n = n(n+1)/2**

Therefore Tall finds = **O(n ^{2})**

**Disjoint set operations Weighted Union**

- Simple Union leads to high time complexity in some cases
- Weighted union is a modified union algorithm with weighting rule
- Widely used to analyze the time complexity of an algorithm in average case
- Weighted union deals with making the smaller tree a subtree of the larger
- If the no.of nodes in the tree with root i is less than the no.of nodes in the tree with root j, then make j the parent of I, otherwise make i the parent of j
- Count of nodes can be placed as a negative number in the P[i] value of the root i

**Collapsing Find**

- SimpleFind() leads to high time complexity in some cases
- CollapsingFind() is a modified version of SimpleFind()
- If j is a node on the path from i to its parent and P[i]!= root, then set j to root

Topic : Disjoint Sets | Disjoint set operations in daa

good

Thank you so much. This is an excellent work. Accuracy can be improved more.