Disjoint Set Algorithm

Disjoint_set.cpp

/*
                                    ALGORITMO DE DISJOINT SET - (C++11)
*/

#include <iostream>
#include <unordered_map>

using namespace std;

class Disjoint_set
{
    private:
        unordered_map<char, char> Parent;
        unordered_map<char, int> Rank; // recorda o foco da arvore
    public:
        Disjoint_set();
        char find(char item)
        {
            if(Parent[item] == item) return item;
            return find(Parent[item]);
        }
        void uniao(char set_1, char set_2)
        {
            if(Rank[set_1] > Rank[set_2])
            {
                Parent[set_2] = set_1;
            }
            else if(Rank[set_1] < Rank[set_2])
            {
                Parent[set_1] = set_2;
            }
            else
            {
                Parent[set_1] = set_2;
                Rank[set_2]++;
            }
        }

        friend ostream &operator<<(ostream &out, Disjoint_set &ds);
};

Disjoint_set::Disjoint_set()
{
    char universo[] = {'a','b','c','d','e'}; //Itens do universo: 'a','b','c','d','e'

    for(char x : universo)
    {
        Parent[x] = x; // Nós temos 5 disjoint sets, cada set contém um item.
        Rank[x] = 0;
    }
    Parent['d'] = 'b'; // 'b' e 'd' são do mesmo set.
    Rank['b'] = 1;
}

ostream &operator<<(ostream &out, Disjoint_set &ds)
{
    out << ds.find('c') << endl  <<
                  ds.find('c') << endl;
    return out;
}


int main(void)
{
    Disjoint_set ds;

  //  ds.find('c'); //retornará c
  //  ds.uniao('c', 'a'); // 'a' e 'c' são do mesmo set
  //  ds.find('c'); //retornará 'a'
  //  ds.uniao('a', 'b'); // 'a', 'c', 'b', 'd' são do mesmo set.

    cout << "Item do universo: " << ds.find('c') << endl;
    ds.uniao('c', 'a');
    cout << "Item do Universo: " << ds.find('c') << endl;
    ds.uniao('a', 'b');
    cout << "Item do Universo: " << ds.find('c') << endl;

    getchar();
    return 0;
}