CODEWITHSUNDEEP
union-find
xotix
xotix

Reputation: 520

Union Find Data Structure Exercise

I just encountered an exercise which I either don't get or has an error in the exersice:

The following table coantains a Union-Find data structre to the set of sets {{1,2,3,9},{4,6,7},{5,8},{10}}. Complement the table s.t. it contains the Union-Find data structure after the operation Union(Find(3),Find(4)).

Now they give me the followint table: (red is te solution)

enter image description here

Now, if I use the table, I get the correct result. What I don't get is, how can 5 be the parent of 7? It's not in the same set, so it isn't possible, is it?

Upvotes: 0

Views: 78

Answers (1)

tryman
tryman

Reputation: 3293

By reconstructing the components from the "initial [parent]" array, the 4 components (sets) are:
(a) 2 <-- 1 --> 3 --> 9
(b) 7 <-- 5 --> 8
(c) 6 --> 4
(d) 10

Therefore the second given set {4,6,7} and the third {5,8} do not seem correctly represented in the "initial [parent]" array. In short, this seems to be a mistake in the exercise.

Upvotes: 1

Related Questions