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

1 /**
2 * Construct the disjoint sets object.
3 * @param numElements the initial number of disjoint sets.
4 */
5 public DisjointSets( int numElements )
6 {
7 s = new int[ numElements ];
8 for( int i = 0; i < s.length; i++ )
9 s[ i ] = -1;
10 }
11
12 /**
13 * Union two disjoint sets using the height heuristic.
14 * root1 and root2 are distinct and represent set names.
15 * @param root1 the root of set 1.
16 * @param root2 the root of set 2.
17 * @throws IllegalArgumentException if root1 or root2
18 * are not distinct roots.
19 */
20 public void union( int root1, int root2 )
21 {
22 assertIsRoot( root1 );
23 assertIsRoot( root2 );
24 if( root1 == root2 )
25 throw new IllegalArgumentException( );
26
27 if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
28 s[ root1 ] = root2; // Make root2 new root
29 else
30 {
31 if( s[ root1 ] == s[ root2 ] )
32 s[ root1 ]--; // Update height if same
33 s[ root2 ] = root1; // Make root1 new root
34 }
35 }
36
37 /**
38 * Perform a find with path compression.
39 * @param x the element being searched for.
40 * @return the set containing x.
41 * @throws IllegalArgumentException if x is not valid.
42 */
43 public int find( int x )
44 {
45 assertIsItem( x );
46 if( s[ x ] < 0 )
47 return x;
48 else
49 return s[ x ] = find( s[ x ] );
50 }

figure 24.21
Implementation of a
disjoint sets class