Structure : Disjoint-set
Disjoint-set data structure (a union–find data structure or merge–find set) is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.
|
// -----------------------------------------------------------------------------
// Disjoint-set C#
// -----------------------------------------------------------------------------
class DisjointSets
{
int[] parent = null;
int[] rank = null;
public DisjointSets(int count)
{
parent = new int[count];
rank = new int[count];
for (int i = 0; i < count; i++)
{
parent[i] = i;
rank[i] = 0;
}
}
public int Find(int x)
{
if (parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}
public void Union(int x, int y)
{
int xroot = Find(x);
int yroot = Find(y);
if (rank[xroot] < rank[yroot]) parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot]) parent[yroot] = xroot;
else
{
parent[yroot] = xroot;
rank[xroot]++;
}
}
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Disjoint-set Python
# ------------------------------------------------------------------------------
class DisjointSets:
def __init__(self, count):
self._parent = [i for i in range(count)]
self._rank = [0 for i in range(count)]
def find(self, x):
if self._parent[x] != x:
self._parent[x] = self.find(self._parent[x])
return self._parent[x]
def union(self, x, y):
xroot = self.find(x)
yroot = self.find(y)
if self._rank[xroot] < self._rank[yroot]:
self._parent[xroot] = yroot
elif self._rank[xroot] > self._rank[yroot]:
self._parent[yroot] = xroot
else:
self._parent[yroot] = xroot
self._rank[xroot] += 1
# ------------------------------------------------------------------------------