Skip to content

Instantly share code, notes, and snippets.

@n1chre
Created January 31, 2017 18:20
Show Gist options
  • Save n1chre/3e3f6f9561345583de01753a040fcce9 to your computer and use it in GitHub Desktop.
Save n1chre/3e3f6f9561345583de01753a040fcce9 to your computer and use it in GitHub Desktop.
Union find with path compression and weighted union
package hruntek;
/**
* Union find with path compression and weighted union
* O(log*N) operations
*/
class UnionFind {
/**
* Node's id
*/
private final int[] id;
/**
* Size of tree below that node
*/
private final int[] size;
/**
* Creates a new union find structure with given number of nodes
*
* @param n number of nodes
*/
UnionFind(int n) {
id = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
size[i] = 1;
}
}
/**
* @param x first node
* @param y second node
* @return true if they are connected
*/
boolean areConnected(int x, int y) {
return find(x) == find(y);
}
/**
* Connects two nodes
*
* @param x first node
* @param y second node
*/
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
// smaller root points to larger one
if (size[rootX] < size[rootY]) {
id[rootX] = rootY;
size[rootY] += size[rootX];
} else {
id[rootY] = rootX;
size[rootX] += size[rootY];
}
}
/**
* Find root node of given node
*
* @param x node
* @return root node
*/
private int find(int x) {
int n = id.length;
if (x < 0 || x >= n) {
throw new IndexOutOfBoundsException("index " + x + " not between 0 and " + (n - 1));
}
return find_(x);
}
/**
* path compression: makes tree almost flat
*/
private int find_(int x){
if (x != id[x]) id[x] = find_(id[x]);
return id[x];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment