'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)
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?
Solution 1:[1]
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.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 |