Skip to content

Instantly share code, notes, and snippets.

@gtke
Created September 2, 2012 22:15
Show Gist options
  • Select an option

  • Save gtke/3605103 to your computer and use it in GitHub Desktop.

Select an option

Save gtke/3605103 to your computer and use it in GitHub Desktop.
Quick Union Algorithm Java Implentation
public class quickUnion {
private int[] id;
public void QuickUnionUF(int N){
id = new int [N];
for(int i = 0; i < N; i++){
id[i] = i;
}
}
private int root(int i){
while (i != id[i]){
i = id[i];
}
return i;
}
public boolean connected(int p, int q){
return root(p) == root(q);
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
id[i] = j;
}
}
@geoguide
Copy link
Copy Markdown

geoguide commented Nov 1, 2017

I don't understand why the root function couldn't just be

private int root(int i){ return id[i]; }

Each union changes the root of the element to the root so wouldn't that make id[i] always the root? And it it doesn't why would i=id[i]; work, satisfying the while loop?

@wilkinsleung0712
Copy link
Copy Markdown

I don't understand why the root function couldn't just be

private int root(int i){ return id[i]; }

Each union changes the root of the element to the root so wouldn't that make id[i] always the root? And it it doesn't why would i=id[i]; work, satisfying the while loop?

The i = id[i] is represent the moving check from its current node to its parent node, it will loop until i == id[i] which by default the number is the parent of itself.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment