PYTHON LANGUAGE

Question

Write a function that receives a disjoint set forest S and prints the number of sets encoded by

S and the size of the largest set in S.

Answer 1

class DisjointSet:

def __init__(self, n):

self.parent = list(range(n))

self.rank = [1] * n

def find(self, x):

if self.parent[x] != x:

self.parent[x] = self.find(self.parent[x]) # Path compression

return self.parent[x]

def union(self, x, y):

rootX = self.find(x)

rootY = self.find(y)

if rootX != rootY:

if self.rank[rootX] > self.rank[rootY]:

self.parent[rootY] = rootX

elif self.rank[rootX] < self.rank[rootY]:

self.parent[rootX] = rootY

else:

self.parent[rootY] = rootX

self.rank[rootX] += 1

def analyze(S):

n = len(S.parent)

set_sizes = {}

for i in range(n):

root = S.find(i)

if root in set_sizes:

set_sizes[root] += 1

else:

set_sizes[root] = 1

num_sets = len(set_sizes)

largest_set_size = max(set_sizes.values())

print("Number of sets:", num_sets)

print("Size of the largest set:", largest_set_size)