In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

**Find:** Determine which set a particular element is in. Also useful for determining if two elements are in the same set.

**Union:** Combine or merge two sets into a single set.

Because it supports these two operations, a disjoint-set data structure is sometimes called a union-find data structure or merge-find set. The other important operation, MakeSet, which makes a set containing only a given element (a singleton), is generally trivial. With these three operations, many practical partitioning problems can be solved. More details read here.

Following is my implementation for disjoint set data structure, which I used in solving lot of problem/puzzles.

class disjoint_sets {
struct disjoint_set {
size_t parent;
unsigned rank;
disjoint_set(size_t i) : parent(i), rank(0) { }
};
std::vector<disjoint_set> forest;
public:
disjoint_sets(size_t n){
forest.reserve(n);
for (size_t i=0; i<n; i++)
forest.push_back(disjoint_set(i));
}
size_t find(size_t i){
if (forest[i].parent == i)
return i;
else {
forest[i].parent = find(forest[i].parent);
return forest[i].parent;
}
}
void merge(size_t i, size_t j) {
size_t root_i = find(i);
size_t root_j = find(j);
if (root_i != root_j) {
if (forest[root_i].rank < forest[root_j].rank)
forest[root_i].parent = root_j;
else if (forest[root_i].rank > forest[root_j].rank)
forest[root_j].parent = root_i;
else {
forest[root_i].parent = root_j;
forest[root_j].rank += 1;
}
}
}
};

### Like this:

Like Loading...

*Related*