Skip to content

Instantly share code, notes, and snippets.

@StevenConradEllis
Created October 2, 2019 07:08
Show Gist options
  • Save StevenConradEllis/2e805f24aa9d27fdf9ce48eed5418c6c to your computer and use it in GitHub Desktop.
Save StevenConradEllis/2e805f24aa9d27fdf9ce48eed5418c6c to your computer and use it in GitHub Desktop.
Quick Union
public class QuickUnion {
private int[] id; // id[i] = parent of i
private int count; // number of components
// instantiate N isolated components 0 through N-1
public QuickUnion(int N) {
id = new int[N];
count = N;
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
// return number of connected components
public int count() {
return count;
}
// return root of component corresponding to element p
public int find(int p) {
while (p != id[p])
p = id[p];
return p;
}
// are elements p and q in the same component?
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// merge components containing p and q
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
id[i] = j;
count--;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment