C++ 中的不相交集 ADT 实现

Question

我在 C++ 中实现不相交集 ADT 时遇到问题，因为我们的老师只解释了并集和查找操作。我完全理解 union 和 find 的概念，但我仍然对如何实现它们感到困惑。

有人可以给我一个实现的想法，并解释一下这个数据结构的接口应该是什么样子吗？

Answer 1

你的要求太多了，我们不是来帮你做作业的。

看看http://en.wikipedia.org/wiki/Disjoint-set_data_struct

Answer 2

#include <iostream>

template<typename T>
class Disjoint_sets
{
public:
    int FIND(int pos);
    bool in_same_set(T data_element_1, T data_element_2);
    void UNION_IF_EQUIVALENT(T data_element_1, T data_element_2);
    void UNION(T data_element_1, T data_element_2);
    Disjoint_sets(bool (*is_equivalent)(T, T));
    Disjoint_sets();
    Disjoint_sets(T* data_arr, bool (*is_equivalent)(T, T),int size);
    void insert(T data_element);
    bool is_root(int pos_number);
    int get_pos(T data_element);
    void partition();
    void print_partition();
private:
    T* data;
    int* parent_pos;
    int* number_of_children;
    int size;
    bool (*isequivalent)(T D1, T D2);
};

template<typename T>
Disjoint_sets<T>::Disjoint_sets()
{
    data = NULL;
    parent_pos = NULL;
    number_of_children = NULL;
    size = 0;
    isequivalent = NULL;
}

template<typename T>
Disjoint_sets<T>::Disjoint_sets(bool (*is_equivalent)(T, T))
{
    isequivalent = is_equivalent;
    data = NULL;
    parent_pos = NULL;
    number_of_children = NULL;
    size = 0;
}

template<typename T>
Disjoint_sets<T>::Disjoint_sets(T* data_arr, bool (*is_equivalent)(T, T), int size)
{
    data = new T[size];
    parent_pos = new int[size];
    number_of_children = new int[size];
    this->size = size;
    isequivalent = is_equivalent;
    for (int i = 0; i < size; i++)
    {
        data[i] = data_arr[i];
        parent_pos[i] = -1;
        number_of_children[i] = 0;
    }
}

template<typename T>
bool Disjoint_sets<T>::is_root(int pos)
{
    if (pos<0 && pos>size - 1)
    {
        std::cout << "Error, invalid pos supplied to is_root\n";
        return false;
    }
    if (parent_pos[pos] == -1)
    {
        return true;
    }
    else
    {
        return false;
    }
}

template <typename T>
int Disjoint_sets<T>::FIND(int pos)
{
    while (!is_root(pos))
    {
        pos = parent_pos[pos];
    }
    return pos;
}

template<typename T>
bool Disjoint_sets<T>::in_same_set(T data_element_1, T data_element_2)
{
    return FIND(get_pos(data_element_1)) == FIND(get_pos(data_element_2));
}

template<typename T>
int Disjoint_sets<T>::get_pos(T data_element)
{
    for (int i = 0; i < size; i++)
    {
        if (data[i] == data_element)
        {
            return i;
        }
    }
    std::cout << "Could not find element\n";
    return -1;
}

template <typename T>
void Disjoint_sets<T>::UNION(T data_element_1, T data_element_2)
{
    int data_parent_1_pos = FIND(get_pos(data_element_1));
    int data_parent_2_pos = FIND(get_pos(data_element_2));
    if ( data_parent_1_pos==data_parent_2_pos )
    {
        return;
    }
    if (number_of_children[data_parent_1_pos] >= number_of_children[data_parent_2_pos])
    {
        parent_pos[data_parent_2_pos] = data_parent_1_pos;
    }
    else
    {
        parent_pos[data_parent_1_pos] = data_parent_2_pos;
    }

}

template <typename T>
void Disjoint_sets<T>::UNION_IF_EQUIVALENT(T data_element_1, T data_element_2)
{
    if (FIND(get_pos(data_element_1)) == FIND(get_pos(data_element_2)))
    {
        return;
    }
    if (isequivalent(data_element_1, data_element_2))
    {
        UNION(data_element_1, data_element_2);
    }
}

template<typename T>
void Disjoint_sets<T>::partition()
{
    for (int i = 0; i < size; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            UNION_IF_EQUIVALENT(data[i], data[j]);
        }
    }
}

template <typename T>
void Disjoint_sets<T>::print_partition()
{
    for (int i = 0; i < size; i++)
    {
        if (is_root(i))
        {
            for (int j = 0; j < size; j++)
            {
                if (FIND(j) == i)
                {
                    std::cout << data[j] << " ";
                }
            }
        }
        std::cout << "\n";
    }
}

template <typename T>
bool lol(int a, int b)
{
    return a * a == b * b;
}

int main()
{
    int arr[6] = { -1,1,2,3,-3,4 };
    Disjoint_sets<int> d(arr,lol<int>, 6);
    d.partition();
    d.print_partition();
}