如何獲得'Disjoint Sets'中所有元素的列表

在我的問題中，我有一堆元素（類元素）。假設我有1000個元素。這些元素最初是不相關的，這意味着它們在自己的集合中。如何獲得'Disjoint Sets'中所有元素的列表

後來我需要使用聯合操作來合併一些基於我的程序流程的這些集合。我打算使用增強庫的disjoint_set（http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html）

我的問題是如何列出給定代表該集合的元素。

Disjoint_set是此類任務的最佳數據結構。那麼我應該考慮使用別的東西嗎？

來源

2014-11-08 mkuse

在看了（新的disjoint_set_ *類）之後，我不認爲他們提供了迭代集合的成員。它們的作用就像從元素到集合代表的單向映射。如果它可以幫助你：http://paste.ubuntu.com/8881626/ – sehe 2014-11-08 10:21:45

從你的散文描述，我沒有得到任何信息，該集合實際上會形成任何圖形。

如果你想要做的是聯營元素與一組，我建議

std::map<ElementId, SetId>

（其中ElementId可能僅僅是Element*如果你知道指針保持有效）。

如果你也希望能夠查詢逆有效

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似乎下來。稍後再添加

來源

2014-11-08 09:54:24 sehe

如何獲得'Disjoint Sets'中所有元素的列表

回答

相關問題