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();
}
}
(defstruct disjoint-set
elements)
(defun make-disjoint-set (elements)
(make-disjoint-set :elements elements))
(defun partition (disjoint-set)
(loop for element in (disjoint-set-elements disjoint-set)
collect
(let ((found (find element (mapcar #'first (rest disjoint-set))
:test #'equal)))
(if found
(acons element element found :test #'equal)
(acons element element nil :test #'equal)))))my @vert = (1..5);
my @edges = ( [1, 2], [2, 3], [4, 5] );
$uf->add( $_ ) for @vert;
$uf->union( $_ ) for @edges;
# find and consolidate partitions into a hash
my %part;
foreach my $v( @vert ) {
my @pa = $uf->find($v);
my $p = shift @pa;
$part{$p} //= [];
push @{ $part{$p} }, $v;
}
foreach my $k (sort keys %part) {
my $vals = join ' ', @{ $part{$k} };
say "$k : $vals";
}
# prints:
# 2 : 1 2 3
# 5 : 4 5
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)