Union-find in action 。Initialize o Everyone is his/her own boss A B D E 0 0 0 0 ●
Union-find in action • Initialize o Everyone is his/her own boss A B C D E 0 0 0 0 0
Union-find in action 。Union(A,B o Find(A)returns A and Find(B)returns B o Make Alice the boss of Bob o Increase the height of the tree A B C D E 1 0 0 0 0 ● ●
Union-find in action • Union(A, B) o Find(A) returns A and Find(B) returns B o Make Alice the boss of Bob o Increase the height of the tree A B C D E 1 0 0 0 0
Union-find in action 。Union(C,D) o Find(C)returns C and Find(D)returns D o Make Carol the boss of Dave o Increase the height of the tree X A B C ← D E 1 0 1 0 ● ●
Union-find in action • Union(C, D) o Find(C) returns C and Find(D) returns D o Make Carol the boss of Dave o Increase the height of the tree A B C D E 1 0 1 0 0
Union-find in action 。Union(B,D】 o Find(B)returns A and Find(D)returns C o Make Alice the boss of Carol o Increase the height of the tree B C D E 2 0 ● ●
Union-find in action • Union(B, D) o Find(B) returns A and Find(D) returns C o Make Alice the boss of Carol o Increase the height of the tree A B C D E 2 0 1 0 0
Your turn 。Find(C? A B C D E 2 0 ●
Your turn • Find(C)? A B C D E 2 0 1 0 0