NAME:

COS 226 Exercises on Union-Find


1. [Exercise 1.5, revised] Draw the resulting tree after running the quick-union algorithm (Program 1.2) on the sequence:   0-2, 1-4, 2-5, 3-6, 0-4, 6-0, 1-3.














2. Which parent-link edges in the final tree from Exercise 1 are not in the original input sequence?






3. Draw a spanning tree that consists only of original input edges from Exercise 1.