-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDisjSets.java
More file actions
86 lines (78 loc) · 2.13 KB
/
DisjSets.java
File metadata and controls
86 lines (78 loc) · 2.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package dp;// DisjSets class
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x ) --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed
/**
* Disjoint set class, using union by rank and path compression.
* Elements in the set are numbered starting at 0.
*
* @author Mark Allen Weiss
*/
public class DisjSets {
private int[] s;
/**
* Construct the disjoint sets object.
*
* @param numElements the initial number of disjoint sets.
*/
public DisjSets(int numElements) {
s = new int[numElements];
for (int i = 0; i < s.length; i++)
s[i] = -1;
}
// Test main; all finds on same output line should be identical
public static void main(String[] args) {
int NumElements = 128;
int NumInSameSet = 16;
DisjSets ds = new DisjSets(NumElements);
int set1, set2;
for (int k = 1; k < NumInSameSet; k *= 2) {
for (int j = 0; j + k < NumElements; j += 2 * k) {
set1 = ds.find(j);
set2 = ds.find(j + k);
ds.union(set1, set2);
}
}
for (int i = 0; i < NumElements; i++) {
System.out.print(ds.find(i) + "*");
if (i % NumInSameSet == NumInSameSet - 1)
System.out.println();
}
System.out.println();
}
/**
* Union two disjoint sets using the height heuristic.
* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
*
* @param root1 the root of set 1.
* @param root2 the root of set 2.
*/
public void union(int root1, int root2) {
if (s[root2] < s[root1]) // root2 is deeper
s[root1] = root2; // Make root2 new root
else {
if (s[root1] == s[root2])
s[root1]--; // Update height if same
s[root2] = root1; // Make root1 new root
}
}
/**
* Perform a find with path compression.
* Error checks omitted again for simplicity.
*
* @param x the element being searched for.
* @return the set containing x.
*/
public int find(int x) {
if (s[x] < 0)
return x;
else
return s[x] = find(s[x]);
}
}