Skip to content

Instantly share code, notes, and snippets.

@tanzaku tanzaku/UnionFind.java Secret
Created Aug 27, 2016

Embed
What would you like to do?
class UnionFind {
private int[] data;
private int[] next;
private int[] last;
public UnionFind(int size) {
data = new int[size];
next = new int[size];
last = new int[size];
clear();
}
public void clear() {
Arrays.fill(data, -1);
Arrays.fill(next, -1);
for(int i = 0; i < last.length; i++) {
last[i] = i;
}
}
public int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); }
public void union(int x, int y) {
if((x = root(x)) != (y = root(y))) {
if(data[y] < data[x]) { final int t = x; x = y; y = t; }
next[last[x]] = y;
last[x] = last[y];
data[x] += data[y];
data[y] = x;
}
}
public boolean same(int x, int y) { return root(x) == root(y); }
public int size(int x) { return -data[root(x)]; }
}
// こんな感じでxと同じ集合の要素がすべて辿れる
for(int i = uf.root(x); i != -1; i = uf.next[i]) {
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.