# C++ class for disjoint-set/union-find on integers

I have implemented the disjoint-set data structure. The purpose is to group integers together. For example, if I want to find out the groups of integers where each adjacent neighbors are same:

vector<vector<int>> test = {
{1,0,0,1},
{0,0,0,1},
{0,3,3,1}};


There are 4 groups of integers, namely:

• Group 1: 1 at (0,0)
• Group 2: 0's at (0,1), (0,2), (1,0), (1,1), (1,2), (2,0)
• Group 3: 1's at (0,3), (1,3), (2,3)
• Group 4: 3's at (2,1), (2,3)

Here is the code in C++:

//This union-find class implements two optimization ideas:
//1)path compression
//2)union by rank

class DisjointSet {
public:
DisjointSet(int num_nodes);
int find(int element);
void do_union(int elment_a, int element_b);
void dup(vector<int> &v);
private:
vector<int> parent_, rank_;
};

DisjointSet::DisjointSet(int num_nodes):
parent_(num_nodes),rank_(num_nodes, 0)
{
for(int i=0; i<num_nodes; ++i) parent_[i] = i;
}

int DisjointSet::find(int element)
{
if(parent_[element] == element) return element;
//1)path compression
return parent_[element] = find(parent_[element]);
}

void DisjointSet::do_union(int a, int b)
{
if(parent_[a] == parent_[b]) return;
int fa = find(a), fb = find(b);
//2)union by rank
if(rank_[fa] < rank_[fb]) {
parent_[fa] = fb;
} else {
parent_[fb] = fa;
if(rank_[fa] == rank_[fb]) rank_[fa]++;
}
}

• Explain how you get from a vector<vector<double>> to "four groups of integers"? How do we interpret test? – 200_success Feb 22 '16 at 22:26
• @200_success I've changed it to vector<vector<int>> basically two integers can be grouped together if the have same value and are adjacent.(but not diagonally) – ijklr Feb 22 '16 at 22:49

Seems pretty straightforward. By the way, "disjoint-set" is a less common name for this data structure than "union-find", at least in my experience.

You have several typos in your code; you should always fix those. Sure, the computer doesn't care, but we don't write C++ code for the computer; we write it for the human reader. elment_a should be element_a; you should either implement dup or remove its declaration; and you should use proper indentation.

class DisjointSet {
public:
DisjointSet(int num_nodes);
int find(int element);
void do_union(int element_a, int element_b);
private:
std::vector<int> parent_;
std::vector<int> rank_;
};


Notice also that I added the missing std::s to your vectors (and by the way you should #include <vector>), and split each member variable declaration onto its own line so that the struct layout is easier to see at a glance.

Who says using rank_ is an optimization? It feels to me like a pessimization, because you're trading O(N) extra space (and more convoluted code) for something like O(lg N) faster lookups. I do see that e.g. Boost.DisjointSet implements "union by rank" as well, but I'd be interested in seeing some benchmark numbers on your particular use-case.

return parent_[element] = find(parent_[element]);


Modern C++ (like modern any-other-language) strongly prefers not to mix side effects into the middle of expressions, except in idiomatic cases such as *p++ = .... Prefer to put the assignment in its own statement.

parent_[element] = find(parent_[element]);
return parent_[element];


int fa = find(a), fb = find(b);


Same deal as above: prefer to put each variable declaration on its own line for readability.

int fa = find(a);
int fb = find(b);


And then use proper indentation in what follows:

if (rank_[fa] < rank_[fb]) {
parent_[fa] = fb;
} else {
parent_[fb] = fa;
if (rank_[fa] == rank_[fb]) rank_[fa]++;
}


Basically, though, looks good. Looks like you picked the right level of abstraction for this particular problem: not too scattered (keeping related things in a nice neat class), but not too libraryish (you hard-code int, for example, instead of going all in with templates).

• >> Who says using rank_ is an optimization? See "Introduction to Algorithms, Second Edition" by Thomas H. Cormen. Chapter 21.3 Disjoint-set forests. There is proof, that using those two heruistics in conjuction makes the running time linear. – nicolai Mar 17 '18 at 7:00