Skip to content

Instantly share code, notes, and snippets.

@karmiclychee
Created June 26, 2014 23:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save karmiclychee/4ff52ec0c8226769d960 to your computer and use it in GitHub Desktop.
Save karmiclychee/4ff52ec0c8226769d960 to your computer and use it in GitHub Desktop.
public int find(int p) {
if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException();
while (p != id[p]) {
id[p] = id[id[p]]; // path compression by halving
p = id[p];
}
return p;
}
@karmiclychee
Copy link
Author

  public int find(int component) {
        // finds the root of the component group
        if (component < 0 || component >= components.length) throw new IndexOutOfBoundsException();
        if (components[component] != component) {
            return find(components[component]);
        } else {
            return component;
        }
    }

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