CODEWITHSUNDEEP
data-structuresunionsdisjoint-sets
Ajay
Ajay

Reputation: 49

how to make sets and solve unions in disjoint set data structures?

i am getting a problem in calculating output of the following question which i got to solve in a quiz. the code is :-

Consider the following program:
for i from 1 to 12:
MakeSet(i)
Union(2, 10)
Union(7, 5)
Union(6, 1)
Union(3, 4)
Union(5, 11)
Union(7, 8)
Union(7, 3)
Union(12, 2)
Union(9, 6)
print(Find(6))
print(Find(3))
print(Find(11))
print(Find(9))

Assume that the disjoint sets data structure is implemented as an array ({\tt smallest}[1 \dots 12]): ({\tt smallest}[i]) is equal to the smallest element in the set containing (i).

What is the output of the following program? As an answer, enter four integers separated by spaces.

After calculating i got the answer as 1 1 2 1 but it is showing it as incorrect. what will be the correct answer??

Upvotes: 2

Views: 3191

Answers (3)

Shobit Jain
Shobit Jain

Reputation: 21

First Disjoint set: 1-6-9 name set as 1,
Second Disjoint set: 2-10-12 name set as 2,
Third Disjoint set: 3-4-5-7-8-11 name set as 3

print(Find(6)) : In set 1
print(Find(3)) : In set 3
print(Find(11)) : In set 3
print(Find(9)) : In set 1

Answer: 1 3 3 1

Upvotes: 2

R Chang
R Chang

Reputation: 63

since Union has the rule: if rank[i_id]>rank[j_id]: assign j under i. we will get the sets as @MBo mentioned thus the answer is 1 3 3 1

Upvotes: 0

MBo
MBo

Reputation: 80177

For such small input you can build sets by hands and get

1 6 9
2 10 12
3 4 5 7 8 11

So only the first and last answers are correct

Upvotes: 0

Related Questions