-
Notifications
You must be signed in to change notification settings - Fork 0
/
UF.java
201 lines (188 loc) · 6.98 KB
/
UF.java
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
/******************************************************************************
* Compilation: javac UF.java
* Execution: java UF < input.txt
* Dependencies: StdIn.java StdOut.java
* Data files: https://algs4.cs.princeton.edu/15uf/tinyUF.txt
* https://algs4.cs.princeton.edu/15uf/mediumUF.txt
* https://algs4.cs.princeton.edu/15uf/largeUF.txt
*
* Weighted quick-union by rank with path compression by halving.
*
* % java UF < tinyUF.txt
* 4 3
* 3 8
* 6 5
* 9 4
* 2 1
* 5 0
* 7 2
* 6 1
* 2 components
*
******************************************************************************/
/**
* The {@code UF} class represents a <em>union–find data type</em>
* (also known as the <em>disjoint-sets data type</em>).
* It supports the classic <em>union</em> and <em>find</em> operations,
* along with a <em>count</em> operation that returns the total number
* of sets.
* <p>
* The union–find data type models a collection of sets containing
* <em>n</em> elements, with each element in exactly one set.
* The elements are named 0 through <em>n</em>–1.
* Initially, there are <em>n</em> sets, with each element in its
* own set. The <em>canonical element</em> of a set
* (also known as the <em>root</em>, <em>identifier</em>,
* <em>leader</em>, or <em>set representative</em>)
* is one distinguished element in the set. Here is a summary of
* the operations:
* <ul>
* <li><em>find</em>(<em>p</em>) returns the canonical element
* of the set containing <em>p</em>. The <em>find</em> operation
* returns the same value for two elements if and only if
* they are in the same set.
* <li><em>union</em>(<em>p</em>, <em>q</em>) merges the set
* containing element <em>p</em> with the set containing
* element <em>q</em>. That is, if <em>p</em> and <em>q</em>
* are in different sets, replace these two sets
* with a new set that is the union of the two.
* <li><em>count</em>() returns the number of sets.
* </ul>
* <p>
* The canonical element of a set can change only when the set
* itself changes during a call to <em>union</em>—it cannot
* change during a call to either <em>find</em> or <em>count</em>.
* <p>
* This implementation uses <em>weighted quick union by rank</em>
* with <em>path compression by halving</em>.
* The constructor takes Θ(<em>n</em>) time, where
* <em>n</em> is the number of elements.
* The <em>union</em> and <em>find</em> operations take
* Θ(log <em>n</em>) time in the worst case.
* The <em>count</em> operation takes Θ(1) time.
* Moreover, starting from an empty data structure with <em>n</em> sites,
* any intermixed sequence of <em>m</em> <em>union</em> and <em>find</em>
* operations takes <em>O</em>(<em>m</em> α(<em>n</em>)) time,
* where α(<em>n</em>) is the inverse of
* <a href = "https://en.wikipedia.org/wiki/Ackermann_function#Inverse">Ackermann's function</a>.
* <p>
* For alternative implementations of the same API, see
* {@link QuickUnionUF}, {@link QuickFindUF}, and {@link WeightedQuickUnionUF}.
* For additional documentation, see
* <a href="https://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class UF {
private int[] parent; // parent[i] = parent of i
private byte[] rank; // rank[i] = rank of subtree rooted at i (never more than 31)
private int count; // number of components
/**
* Initializes an empty union-find data structure with
* {@code n} elements {@code 0} through {@code n-1}.
* Initially, each element is in its own set.
*
* @param n the number of elements
* @throws IllegalArgumentException if {@code n < 0}
*/
public UF(int n) {
if (n < 0) throw new IllegalArgumentException();
count = n;
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
/**
* Returns the canonical element of the set containing element {@code p}.
*
* @param p an element
* @return the canonical element of the set containing {@code p}
* @throws IllegalArgumentException unless {@code 0 <= p < n}
*/
public int find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // path compression by halving
p = parent[p];
}
return p;
}
/**
* Returns the number of sets.
*
* @return the number of sets (between {@code 1} and {@code n})
*/
public int count() {
return count;
}
/**
* Returns true if the two elements are in the same set.
*
* @param p one element
* @param q the other element
* @return {@code true} if {@code p} and {@code q} are in the same set;
* {@code false} otherwise
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
* @deprecated Replace with two calls to {@link #find(int)}.
*/
@Deprecated
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* Merges the set containing element {@code p} with the set
* containing element {@code q}.
*
* @param p one element
* @param q the other element
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make root of smaller rank point to root of larger rank
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
// validate that p is a valid index
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
/**
* Reads an integer {@code n} and a sequence of pairs of integers
* (between {@code 0} and {@code n-1}) from standard input, where each integer
* in the pair represents some element;
* if the elements are in different sets, merge the two sets
* and print the pair to standard output.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int n = StdIn.readInt();
UF uf = new UF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.find(p) == uf.find(q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}