Union find using unordered map and templates in C++ I tried to implement union find (disjoint set data structure) algorithm in C++. There I used unordered_map data structure. Is there a better way of doing this using any other data structure.

While finding the root I have used the following way.

int root(int i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }


Also, I can implement it as

int root(int i){
        while (i != parent[i]){
            parent[i] = parent[parent[i]]);
            i = parent[i];
        }
        return i;
    }


It seems like both are same other than the (recursive and iterative) approach for me. Which is better here!

The following is my implementation.

#include&lt;iostream&gt;
#include&lt;unordered_map&gt;
#include&lt;vector&gt;
using namespace std;

class Disjoinset{

    private:

    unordered_map&lt;int, int&gt; parent, rank;
    // find the root
    int root(int i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }

    public:

    // initialize the parent map
    void makeSet(int i){
        parent[i] = i;
    }
    // check for the connectivity
    bool is_connected(int p, int q){
        return root(p) == root(q);
    }
    // make union of two sets
    void Union(int p, int q){

        int proot = root(p);
        int qroot = root(q);

        if(proot == qroot) return;

        if(rank[proot] &gt; rank[qroot]) {
            parent[qroot] = proot;
        }
        else{
            parent[proot] = qroot;
            if(rank[proot] == rank[qroot]) rank[qroot]++;
        }
    }
};



Driver code

int main(){
    vector&lt;int&gt; arr = {1,2,9,8,6,5,7};
    Disjoinset dis; // create a disjoint set object
    for(int x: arr){
        dis.makeSet(x); // make the set
    }
    dis.Union(1,9); // create connections
    dis.Union(6,5);
    dis.Union(7,9);
    cout &lt;&lt;  dis.is_connected(1,7) &lt;&lt; endl; // check the connectivity.
    cout &lt;&lt;  dis.is_connected(1,6) &lt;&lt; endl;
    return 0;
}


Thereafter I tried to use generics and I came up with following. Can someone help me on this as I am new to C++. Is my implementation is correct or are there any better approach.

#include&lt;iostream&gt;
#include&lt;unordered_map&gt;
#include&lt;vector&gt;
#include&lt;string&gt;
using namespace std;

template&lt;class T&gt;
class Disjoinset{

    private:

    unordered_map&lt; T, T&gt; parent; 
    unordered_map&lt; T, int&gt;rank;
    // find the root
    T root(T i){
        if(i != parent[i]) parent[i] = root(parent[i]);
        return parent[i];
    }

    public:

    // initialize the parent map
    void makeSet(T i){
        parent[i] = i;
    }
    // check for the connectivity
    bool is_connected(T p, T q){
        return root(p) == root(q);
    }
    // make union of two sets
    void Union(T p, T q){

        T proot = root(p);
        T qroot = root(q);

        if(proot == qroot) return;

        if(rank[proot] &gt; rank[qroot]) {
            parent[qroot] = proot;
        }
        else{
            parent[proot] = qroot;
            if(rank[proot] == rank[qroot]) rank[qroot]++;
        }
    }
};


int main(){
    vector&lt;string&gt; arr = {"amal", "nimal", "kamal", "bimal", "saman"};
    Disjoinset &lt;string&gt;dis; // create a disjoint set object
    for(string x: arr){
        dis.makeSet(x); // make the set
    }
    dis.Union("amal", "kamal"); // create connections
    dis.Union("kamal", "nimal");
    cout &lt;&lt;  dis.is_connected("amal", "nimal") &lt;&lt; endl; // check the connectivity.
    cout &lt;&lt;  dis.is_connected("bimal", "amal") &lt;&lt; endl;
    return 0;
}



Thank you for every answer.
Overall, that looks good to me. A few nitpicks, however, follow:

Advice 1

#include&lt;iostream&gt;
#include&lt;unordered_map&gt;
#include&lt;vector&gt;
#include&lt;string&gt;


I would put a space between e and &lt;. Also, I would sort the rows alphabetically, so that we get:

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;unordered_map&gt;
#include &lt;vector&gt;


Advice 2: One template per file

I would extract away the main and put the entire disjoint set template into its own file; call it DisjointSet.hpp to begin with.

Advice 3: Protect your header files from multiple inclusion

I would most definitely put the header guards in DisjointSet.hpp so that it looks like this:

#ifndef COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
#define COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
.
. Your funky DisjointSet.hpp code here. :-)
.
#endif // COM_STACKEXCHANGE_RUSIRU_UTIL_HPP


Advice 4: "Package" your code into namespaces

I have a habit of putting my data structures into relevant namespaces in order to avoid name collisions with other people's code:

namespace com::stackexchange::rusiru::util {
    template&lt;class T&gt;
    class DisjointSet {
        ...
    };
}


Advice 5: Remove minor noise

unordered_map&lt; T, T&gt; parent; 
unordered_map&lt; T, int&gt;rank;


I would write:

unordered_map&lt;T, T&gt; parent;
unordered_map&lt;T, int&gt; rank;


Note the placement of spaces!

Advice 6: Arbitrary method naming scheme

Essentially, you have makeSet, is_connected, Union. That's three different method naming schemes right there; choose one and stick to it. For example, makeSet, isConnected, union.

Advice 7: Printing booleans to stdout:

You can do cout &lt;&lt; std::boolalpha &lt;&lt; ...; in order to print true/false.

Advice 8: Don't pollute your namespace

Generally speaking, using namespace std; is not what you may see in professional C++ code. Consider using individual uses such as:

using std::cout;
using std::endl;


Putting all together

Overall, I had this in mind:

DisjointSet.hpp

#ifndef COM_STACKEXCHANGE_RUSIRU_UTIL_HPP
#define COM_STACKEXCHANGE_RUSIRU_UTIL_HPP

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;unordered_map&gt;
#include &lt;vector&gt;

namespace com::stackexchange::rusiru::util {

    using std::boolalpha;
    using std::cout;
    using std::endl;
    using std::string;
    using std::unordered_map;
    using std::vector;

    template&lt;typename T&gt;
    class DisjointSet {

    private:

        unordered_map&lt;T, T&gt; parent;
        unordered_map&lt;T, int&gt; rank;

        // find the root
        T root(T i) {
            if (i != parent[i]) parent[i] = root(parent[i]);
            return parent[i];
        }

    public:

        // initialize the parent map
        void makeSet(T i) {
            parent[i] = i;
        }
        // check for the connectivity
        bool isConnected(T p, T q) {
            return root(p) == root(q);
        }
        // make union of two sets
        void union(T p, T q) {

            T proot = root(p);
            T qroot = root(q);

            if (proot == qroot) return;

            if (rank[proot] &gt; rank[qroot]) {
                parent[qroot] = proot;
            }
            else {
                parent[proot] = qroot;
                if (rank[proot] == rank[qroot]) rank[qroot]++;
            }
        }
    };
}

#endif // COM_STACKEXCHANGE_RUSIRU_UTIL_HPP


main.cpp

#include "DisjointSet.hpp"
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

using std::boolalpha;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using com::stackexchange::rusiru::util::DisjointSet;

int main() {
    vector&lt;string&gt; arr = { "amal", "nimal", "kamal", "bimal", "saman" };
    DisjointSet&lt;string&gt; dis; // create a disjoint set object

    for (const string x : arr) {
        dis.makeSet(x); // make the set
    }

    dis.union("amal", "kamal"); // create connections
    dis.union("kamal", "nimal");

    cout &lt;&lt; boolalpha &lt;&lt; dis.isConnected("amal", "nimal") &lt;&lt; endl; // check the connectivity.
    cout &lt;&lt; dis.isConnected("bimal", "amal") &lt;&lt; endl;
    return 0;
}