c++ - 使用 STL C++ 制作传递对集

Question

我想创建一个具有传递对的集合。我的输入将是形式pair<int, int>，我需要一个集合，其中包含给定输入的所有传递对。例如，如果我有对 {1, 2} {2, 1} {2, 3} {3,4} 作为输入，那么我需要有一个包含对 { {1,2}, {2, 1}、{1、3}、{3、4}、{1、4}、{2、4}}。我还需要找出给定的对是否是这个传递集的成员。是否有任何内置数据结构/STL 库可以让我在 C++ 中完成此任务？

Answer 1

你有一个图，你想把它变成一个自由类别，也就是那个图的传递闭包。

您的int对元素是顶点，对本身是边，这就是您的图。现在，图上的一个自由类别是具有边组合定律的图，以及可以由该定律产生的所有附加边。法律说

• 如果有一条边（或范畴论命名的“箭头”）f从a到b
• 和一条g从b到的边c
• 然后有另一个边表示f∘g从a到c
• 组合是关联的 ( (f∘g)∘h = f∘(g∘h))

（每个类别也有单位边，表示每个顶点1a从a到，还有一条定律说，对于从到，的每个箭头，但我们不是在谈论这些）。aafab1a∘f = f∘1b= f

_{特此完成本答案的通识教育部分。}

C++ 标准库中没有相关算法，但您可能需要检查boost::graph或任何其他面向图的库。boost::graph有transitive_closure正是你想要的方法。

Answer 2

您可以使用以下方式表示您的集合：

set<pair<int, int>> myset;

然后可以使用以下公式计算传递闭包：

void transitive_closure(set<pair<int, int>>& s)
{
    set<pair<int, int>> a;   // missing nodes to add
    for (auto i = s.cbegin(); i != s.cend(); i++)
    {
        for (auto j = i; ++j != s.cend(); j)
        {
            if (i->second == j->first 
                  && i->first != j->second 
                  && s.count(make_pair(i->first, j->second))==0 )
                a.insert(make_pair(i->first, j->second));
        }
    }
    if (!a.empty()) {
        for (auto p : a)
            s.insert(p);
        transitive_closure(s);
    }
}

它不是最优化的算法，因为递归会重复一些比较。但它有效。顺便说一句，我认为您在结果集中忘记了 {2, 3}。

要检查一对是否属于集合，只需检查是否s.count(make_pair(i->first, j->second)!=0