Skip to content

Instantly share code, notes, and snippets.

@StevenConradEllis
Created October 2, 2019 07:02
Show Gist options
  • Save StevenConradEllis/824954891b917e3d7d2dff48ea39c008 to your computer and use it in GitHub Desktop.
Save StevenConradEllis/824954891b917e3d7d2dff48ea39c008 to your computer and use it in GitHub Desktop.
Quick Find
public class QuickFind {
private int[] id;
private int count;
public QuickFind(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
public boolean connected(int p, int q) {
return id[p] == id[q];
}
public int count() {
return count;
}
// Return component identifier for component containing p
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
if (connected(p, q)) return;
int pid = id[p];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = id[q];
count--;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment