|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(not
as much work as it looks)
|
|
|
| |
Perform
Disjoint Union-Find operations on Up-Tree with
|
|
|
path
compression and using weight (# of nodes) in merges.
|
|
|
| |
Starting
with empty tree.
|
|
|
| |
Keep
track of (sub)tree weight, and pointers into tree
|
|
|
(pointers
isnt too hard)
|
|
|
| |
Vaguely
have a sense of # of operations (e.g. edge
|
|
|
traversals)
|
|
|
| |
For
items: a,b,c,d,e,f,g,h,i,j,k
|
|
|
| |
Union
(a,b). Union (b,c). Union (d,e). Union (d,f).
|
|
|
Union
(d,j). Union (d,k). Union (e,g). Union (h,i). Union
|
|
(c,h). Union (c,f). Find (i). Find
(b). Find (c). Find (i).
|
|
|
Find
(h).
|
|
|
|
