如何从“不相交的集合”所有的元素列表 [英] How to get list of all elements from a 'Disjoint Sets'
问题描述
在我的问题,我有一大堆的元素(类元素)。说我有1000元。这些元素是最初无关联的,这意味着他们在自己套。
In my problem, I have a bunch of Elements (Class Element). Say I have 1000 Elements. These Elements are initially un-associated which means they are in their own sets.
后来,我需要使用union操作合并一些基于我的程序流程,这些套。
我打算使用Boost库的disjoint_set( HTTP:// WWW。 boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html )
Later I need to use the union operation to merge some of these sets based of my program flow. I plan to use the boost library's disjoint_set (http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html)
我的问题是怎么可能列出给出的一组重新presentative一组元素。
My question is how is it possible to list the Elements in a set given the representative of the set.
时disjoint_set用于这种任务的最佳数据结构。所以,我应该考虑用别的东西?
Is disjoint_set the best data structure for such a task. So should I look into using something else?
推荐答案
从你的文字描述,我没有得到任何信息,该套实际上形成任何图形。
From your prose description, I get no information that the sets would actually form any graphs.
如果你想要做的就是联想的元素与一组,我建议
If all you want to do is associate Elements with a set, I'd suggest
std::map<ElementId, SetId>
(其中 ElementId
可能仅仅是元素*
如果你知道指针仍然有效)。
(where ElementId
could simply be Element*
if you know the pointers stay valid).
如果您还希望能够有效地查询逆
If you also want to be able to query the inverse efficiently
bimap<Element, bimaps::multiset_of<SetId> >
将是一个候选人。看到一个示范<罢工> 住在Coliru 行使>¹
#include <boost/range/iterator_range.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/bimap.hpp>
#include <iostream>
using namespace boost;
int main() {
using Element = int; // for simplicity :)
using SetId = int;
using Sets = bimap<Element, bimaps::multiset_of<SetId> >;
Sets sets;
sets.insert({ Element(1), 300 });
sets.insert({ Element(2), 300 });
sets.insert({ Element(3), 400 });
sets.insert({ Element(4), 300 });
// give us set #300
for (auto& e : make_iterator_range(sets.right.equal_range(300)))
std::cout << e.first << " - Element(" << e.second << ")\n";
}
打印
300 - Element(1)
300 - Element(2)
300 - Element(4)
¹Coliru似乎下来。之后会添加
¹ Coliru seems down. Will add later
这篇关于如何从“不相交的集合”所有的元素列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!