c++ - 用C++设置合并算法

Question

假设现在你有一组数据:

Data 1: (1, 2);
Data 2: (1, 3);
Data 3: (7, 8);
Data 4: (8, 20);

现在的任务是合并数据集，如果它与另一个数据集有共同的元素。在我们的示例中，数据 1 将与数据 2 合并，因为它们共享公共(public)编号 1。数据 3 和数据 4 也是如此。我的问题是我们如何在 C++ 中非常高效地实现此功能。目前我的实现是基于 std::vector > 数据结构，如下代码所示:

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>


using namespace std;
bool find_the_element(const set<int> &mysets, const vector<int> &myvector)
{
    for(int i=0; i<myvector.size(); i++)
    {
        set<int>::iterator it;
        it = mysets.find(myvector[i]);
        if (it != mysets.end())
            return true;
    }
    return false;

}





int main () 
{



    set<vector<int> > myset;
    vector<int> a;
    a.push_back(1);
    a.push_back(2);

    vector<int> b;
    b.push_back(1);
    b.push_back(3);

    vector<int> c;
    c.push_back(7);
    c.push_back(8);

    vector<int> d;
    d.push_back(8);
    d.push_back(20);
    vector<vector<int> > my_vector_array;
    my_vector_array.push_back(a);
    my_vector_array.push_back(b);
    my_vector_array.push_back(c);
    my_vector_array.push_back(d);


    vector<set<int> > my_sets;
    for(int i=0; i<my_vector_array.size(); i++)
    {
        vector<int> temp_vector = my_vector_array[i];

        if (my_sets.empty())
        {
            set<int> temp_set;
            for(int j=0; j<temp_vector.size(); j++)
                temp_set.insert(temp_vector[j]);

            my_sets.push_back(temp_set);
        }
        else
        {
            bool b_find = false;
            for(int j=0; j<my_sets.size(); j++)
            {
                set<int>temp_set;
                temp_set = my_sets[j];
                if (find_the_element(temp_set,temp_vector))
                {
                    b_find = true;
                    my_sets[j].insert(temp_vector.begin(), temp_vector.end());

                    break;
                }

            }
            if (b_find)
            {
                // something already done
            }
            else
            {
                set<int> temp_set;
                for(int j=0; j<temp_vector.size(); j++)
                    temp_set.insert(temp_vector[j]);

                my_sets.push_back(temp_set);
            }

        }
    }
}

我想知道 C++ 中是否有更有效的数据结构或更有效的算法来完成这项工作。谢谢!

Answer 1

实现可快速合并的集合的最有效方法之一是使用 Disjoint-set Data Structure .

想法是将每个集合最初表示为一个链表，链表的头部作为整个集合的标识符。随着集合的合并，节点被重新指向头部以加速进一步的搜索。

链接处的文章有伪代码； C++ 实现应该不会太困难。

您需要保留一个单独的 map，将您目前看到的整数与其在不相交集森林中的节点连接起来。您将遍历您的数据集，一项一项地获取它们的项目，在 map 中查找项目，然后按照指向其集的链接，或者创建一个新的“单例”不相交集您要添加的项目。