Be concise.
Be useful.
All contributions dictatorially edited by webmasters to match personal tastes.
Please do not paste any copyright violating material.
Please try to avoid dependencies to third-party libraries and frameworks.
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(); } }
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)