基于其值的自定义排序向量

Question

我有以下向量:

std::vector< std::pair<int, int> > vectorOfPairs

包括以下项目:

0, 1
0, 2
1, 4
2, 3
3, 4
4, 5
5, 6

我想以一种方式对它们进行排序,即每对中的第二个分量等于向量中最近对的第一个分量,如下所示:

0, 1
1, 4
4, 5
5, 6
0, 2
2, 3
3, 4

我不知道这是否足够明显,我会附上一张图片,显示我正在尝试做的事情:

我觉得我应该使用sort某种比较器,但我迷失在这里:

std::sort(vectorOfPairs.begin(), vectorOfPairs.end(), MyComparator);

---

bool MyComparator(pair<int, int> a, pair<int, int> b) {
    if(some_kind_of_comparison){
        return true;
    } 
    return false;
}

我是c ++的新手,如果有人可以帮我解决如何做到这一点的伪代码,我将非常感激.

Answer 1

您可以将此问题视为图形问题.每个对都代表有向图中的边.例如,对(0,2)表示"从节点0到节点2有一条边",而对(2,5)表示"从节点2到节点5有一条边".

如果以这种方式考虑事物,每对的第二个元素与下一对的第一个元素匹配的一系列边对应于图中的路径.例如,您给出的排序顺序中有两个路径:0 - > 1 - > 4 - > 5 - > 6和0 - > 2 - > 3 - > 4.因此,您尝试的问题求解如下:如何将图中的边缘分成最小数量的边缘不相交路径？一旦你解决了这个问题,你就可以按照你想要做的任何顺序输出这些路径.

你无法解决这个问题std::sort.例如,假设您有边(0,1),(0,2),(2,3)和(1,3).在这种情况下,这两个顺序都是有效的:

(0, 1)          (0, 2)
(1, 3)          (2, 3)
(0, 2)          (0, 1)
(2, 3)          (1, 3)

这是个问题.因为(0,1)在第一个排序中位于(0,2)之前,而(0,2)在第二个排序中位于(0,1)之前,所以比较器可能是严格弱排序的唯一方法是if(0,1) )和(0,2)是无法比拟的.这意味着在任何排序的排序中,(0,1)和(0,2)(包括)之间的所有元素也必须是无法比较的,因为不可比性的传递性.换句话说,我们应该能够采取任何排序,置换(0,1)和(0,2)(包括)之间的元素,并获得新的排序.这意味着这应该是一个有效的排序,即使它不是因为有一个非常好的解决方案:

(0, 1)          (0, 1)
(1, 3)   -->    (0, 2)
(0, 2)          (1, 3)
(2, 3)          (2, 3)

所以没有办法解决这个问题std::sort.

我不确定的是解决这个问题的最佳方法是什么.这似乎与流量问题有关,但我不确定如何设置它.如果我想到任何事情,我会更新这个答案.感谢您发布有趣的内容!