Skip to content

Instantly share code, notes, and snippets.

@StevenConradEllis
Created October 2, 2019 07:10
Show Gist options
  • Save StevenConradEllis/904bdc53b8a7e7bd5c560a36e5145d56 to your computer and use it in GitHub Desktop.
Save StevenConradEllis/904bdc53b8a7e7bd5c560a36e5145d56 to your computer and use it in GitHub Desktop.
Weighted Quick Union
public class WeightedQuickUnion {
private int[] id; // id[i] = parent of i
private int[] sz; // sz[i] = number of objects in subtree rooted at i
private int count; // number of components
// Create an empty union find data structure with N isolated sets.
public WeightedQuickUnion(int N) {
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}
// Return the number of disjoint sets.
public int count() {
return count;
}
// Return component identifier for component containing p
public int find(int p) {
while (p != id[p])
p = id[p];
return p;
}
// Are objects p and q in the same set?
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// Replace sets containing p and q with their union.
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
// make smaller root point to larger one
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment