Я пробовал этот вопрос 20 раз, но до сих пор не получил ответ

Question

Вопрос связан с множествами и объединениями из курса структур данных

Рассмотрим следующую программу:

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))

Я получил 9 7 7 9 за этот вопрос, но это неправильно.

Answer 1

Я гуглил Union-Find и приземлился по алгоритму DisjointSet.

После вызовов объединения генерируются следующие 3 набора:

7 -> 5, 8, 3
5 -> 11
3 -> 4

9 -> 6
6 -> 1

12 -> 2
2 -> 10

Find (6), Find (3), Find (11), Find (9)

Каждый из этих вызовов находит верхнего родителя по этому номеру, поэтому результат равен: 9, 7, 7, 9 НО.Это предполагает, что моя реализация Union соответствует фактической реализации Union.Те же самые наборы будут генерироваться любой реализацией, но их верхний родитель будет отличаться.