Augmented linked-list solution Store set S=x1,x2,.,xk as unordered doubly linked list. Define reps i to be front of list, x Each element x, also stores pointer rep[x, to reps rep S:[[…口 reps FiND-SEtX returns repx ⊙(1) UNION(x, y) concatenates the lists containing x and y, and updates the rep pointers for all elements in the list containing y ⊙(n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.6© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.6 Augmented linked-list solution Si : x … 1 x2 xk rep[Si] rep Store set Si = {x1, x2, …, xk} as unordered doubly linked list. Define rep[Si] to be front of list, x1. Each element xj also stores pointer rep[xj] to rep[Si]. • FIND-SET(x) returns rep[x]. • UNION(x, y) concatenates the lists containing x and y, and updates the rep pointers for all elements in the list containing y. – Θ(n) – Θ(1)