Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
class UnionFind {
vector<int> pir;
public:
UnionFind(int size) : pir(size, -1) { }
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (pir[y] < pir[x]) swap(x, y);
pir[x] += pir[y];
pir[y] = x;
}
}
bool same(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
if (pir[x] < 0) {
return x;
} else {
return pir[x] = root(pir[x]);
}
}
int size(int x) {
return -pir[root(x)];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment