Idiom #187 Disjoint Set
Disjoint Sets hold elements that are partitioned into a number of disjoint (non-overlapping) sets.
class UnionFind:
def __init__(self, size):
self.rank = [0] * size
self.p = [i for i in range(size)]
def find_set(self, i):
if self.p[i] == i:
return i
else:
self.p[i] = self.find_set(self.p[i])
return self.p[i]
def is_same_set(self, i, j):
return self.find_set(i) == self.find_set(j)
def union_set(self, i, j):
if not self.is_same_set(i, j):
x, y = self.find_set(i), self.find_set(j)
public class DisjointSetElement {
private DisjointSetElement representative = this;
public DisjointSetElement getRepresentative() {
if (representative != this) {
representative = representative.getRepresentative();
}
return representative;
}
public void union(DisjointSetElement other) {
other.getRepresentative().representative = getRepresentative();
}
}