The disjoint set class - Data Structures and Problem Solving Using Java - page 904

1 // Nearest Common Ancestors algorithm
2 //
3 // Preconditions (and global objects):
4 // 1. union/find structure is initialized
5 // 2. All nodes are initially unmarked
6 // 3. Preorder numbers are already assigned in num field
7 // 4. Each node can store its marked status
8 // 5. List of pairs is globally available
9
10 DisjSets s = new DisjSets( treeSize ); // union/find

Node [ ] anchor = new Node[ treeSize ]; // Anchor node for each set

11

12
13

// main makes the call NCA( root )

// after required initializations 14

15
16 void NCA( Node u )
17 {
18 anchor[ s.find( u.num ) ] = u;
19
20 // Do postorder calls
21 for( each child v of u )
22 {
23 NCA( v );
24 s.union( s.find( u.num ), s.find( v.num ) );
25 anchor[ s.find( u.num ) ] = u;
26 }
27
28 // Do nca calculation for pairs involving u
29 u.marked = true;
30 for( each v such that NCA( u, v ) is required )
31 if( v.marked )
32 System.out.println( "NCA( " + u + ", " + v +
33 " ) is " + anchor[ s.find( v.num ) ] );
34 }

figure 24.11
Pseudocode for the nearest common ancestors problem

the quick-find algorithm

24.3

In this section and Section 24.4 we lay the groundwork for the efficient
implementation of the union/find data structure. There are two basic strat-
egies for solving the union/find problem. The first approach, the quick-find
algorithm, ensures that the find instruction can be executed in constant
worst-case time. The other approach, the quick-union algorithm, ensures