c++ - 理解 boost::disjoint_sets

Question

我需要使用 boost::disjoint_sets，但是 the documentation我不清楚。有人可以解释一下每个模板参数的含义，或者给出一个创建disjoint_sets的小示例代码吗？

根据要求，我正在使用 disjoint_sets 来实现 Tarjan's off-line least common ancestors algorithm ，即 - 值类型应该是 vertex_descriptor。

Answer 1

我可以从文档中理解:

不相交需要将等级和父级(在森林树中)关联到每个元素。由于您可能想要处理任何类型的数据，例如，您可能并不总是想为父级使用映射:使用整数数组就足够了。您还需要每个元素的等级( union 查找所需的等级)。

你需要两个“属性”:

• 将一个整数与每个元素(第一个模板参数)相关联，排名
• 将一个元素关联到另一个元素(第二个模板参数)，父亲

举个例子:

std::vector<int>  rank (100);
std::vector<int>  parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);

数组使用&rank[0],&parent[0]到模板中的类型为int*

对于更复杂的示例(使用 map )，您可以查看 Ugo 的答案。

你只是给算法两个结构来存储他需要的数据(等级/父级)。