$**$Please only answer the #your code here$**$

class DisjointForests:

def $\_\_$init$\_\_($self$,$ n$)$:

assert n $>=1,\text{'}$ Empty disjoint forest is disallowed'

self.n $=$ n

self.parents $=[$None$]*$n

self.rank $=[$None$]*$n

# Function: dictionary$\_$of$\_$sets

# Convert the disjoint forest structure into a dictionary d

# wherein d has an entry for each representative i

# d$[$i$]$ maps to each elements which belongs to the tree corresponding to i

# in the disjoint forest.

def dictionary$\_$of$\_$sets$($self$)$:

d $=\{\}$

for i in range$($self$.$n$)$:

if self.is$\_$representative$($i$)$:

d$[$i$]=$ set$([$i$])$

for j in range$($self$.$n$)$:

if self.parents$[$j$]!=$ None:

root $=$ self.find$($j$)$

assert root in d

d$[$root$].$add$($j$)$

return d

def make$\_$set$($self$,$ j$)$:

assert $0<=$ j $<$ self.n

assert self.parents$[$j$]==$ None, 'You are calling make$\_$set on an element multiple times $--$ not allowed.$\text{'}$

self.parents$[$j$]=$ j

self.rank$[$j$]=1$

def is$\_$representative$($self$,$ j$)$:

return self.parents$[$j$]==$ j

def get$\_$rank$($self$,$ j$)$:

return self.rank$[$j$]$

# Function: find

# Implement the find algorithm for a node j in the set.

# Repeatedly traverse the parent pointer until we reach a root.

# Implement the "rank compression" strategy by making all

# nodes along path from j to the root point directly to the root.

def find$($self$,$ j$)$:

assert $0<=$ j $<$ self.n

assert self.parents$[$j$]!=$ None, 'You are calling find on an element that is not part of the family yet. Please call make$\_$set first.$\text{'}$

# your code here

# Function : union

# Compute union of j$1$ and j$2$

# First do a find to get to the representatives of j$1$ and j$2.$

# If they are not the same, then

# implement union using the rank strategy I.e$,$ lower rank root becomes

# child of the higher ranked root.

# break ties by making the first argument j$1\text{'}$s root the parent.

def union$($self$,$ j$1,$ j$2)$:

assert $0<=$ j$1<$ self.n

assert $0<=$ j$2<$ self.n

assert self.parents$[$j$1]!=$ None

assert self.parents$[$j$2]!=$ None

# your code here

Test:

d $=$ DisjointForests$(10)$

for i in range$(10)$:

d$.$make$\_$set$($i$)$

for i in range$(10)$:

assert d$.$find$($i$)==$ i$,$ f'Failed: Find on $\{$i$\}$ must return $\{$i$\}$ back'

d$.$union$(0,1)$

d$.$union$(2,3)$

assert$($d$.$find$(0)==$ d$.$find$(1)),\text{'}0$ and $1$ have been union$-$ed together'

assert$($d$.$find$(2)==$ d$.$find$(3)),\text{'}2$ and $3$ have been union$-$ed together'

assert$($d$.$find$(0)!=$ d$.$find$(3)),\text{'}0$ and $3$ should be in different trees'

assert$(($d$.$get$\_$rank$(0)==2$ and d$.$get$\_$rank$(1)==1)$ or

$($d$.$get$\_$rank$(1)==2$ and d$.$get$\_$rank$(0)==1)),$ 'one of the nodes $0$ or $1$ must have rank $2\text{'}$

assert$(($d$.$get$\_$rank$(2)==2$ and d$.$get$\_$rank$(3)==1)$ or

$($d$.$get$\_$rank$(3)==2$ and d$.$get$\_$rank$(2)==1)),$ 'one of the nodes $2$ or $3$ must have rank $2\text{'}$

d$.$union$(3,4)$

assert$($d$.$find$(2)==$ d$.$find$(4)),\text{'}2$ and $4$ must be in the same set in the family.$\text{'}$

d$.$union$(5,7)$

d$.$union$(6,8)$

d$.$union$(3,7)$

d$.$union$(0,6)$

assert$($d$.$find$(6)==$ d$.$find$(1)),\text{'}1$ and $6$ must be in the same set in the family'

assert$($d$.$find$(7)==$ d$.$find$(4)),\text{'}7$ and $4$ must be in the same set in the family'

print$(\text{'}$All tests passed: $10$ points.$\text{'})$