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)
Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD rep P [十 reps, c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.7
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.7 Example of augmented linked-list solution Sx : x1 x2 rep[Sx] rep Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. Sy : y1 y2 y3 rep[Sy] rep
Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD 囗口s rep P 凹[ reps, c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.8
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.8 Example of augmented linked-list solution Sx ∪ Sy : x1 x2 rep[Sx] rep Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. y1 y2 y3 rep[Sy] rep
Example of augmented linked-list solution Each element x, stores pointer reply] to rep[si UNION(x, y) concatenates the lists containing x and y and updates the rep pointers for all elements in the list containing y reD 囗口s repS, 凹[[口 c 2001 by erik D. Demaine Introduction to Ago orns Day33L20.9
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.9 Example of augmented linked-list solution Sx ∪ Sy : x1 x2 rep[Sx ∪ Sy] Each element xj stores pointer rep[xj] to rep[Si]. UNION(x, y) • concatenates the lists containing x and y, and • updates the rep pointers for all elements in the list containing y. y1 y2 y3 rep