众所周知 std::sort 和 std::stable_sort 的比较函数都要求满足 Compare,其中一条要求是传递性(应该可以这么叫)
若 comp(a, b) == true 且 comp(b, c) == true 则 comp(a, c) == true
但是本题的操作 1 并不满足这一点,因为显然,即使 a 和 b 之间的边方向是 a→b 且 b 和 c 之间的边方向是 b→c,也不影响 a 和 c 之间的边的方向,完全有可能出现 comp(a, b) == true 且 comp(b, c) == true 且 comp(a, c) == false 的情况。
实际上因为只需要找一条哈密顿路径,不满足这一点也可以进行这种类似排序的操作,所以我手写了快速排序通过本题。
但是题解区有代码使用了 stable_sort,理论上会导致 RE 等各种情况,实际上我测试了发现 sort 和 stable_sort 都能通过,这是否说明只要满足类似本题中的一些特殊性质,这样使用也不会出问题?