我有一组有序对 (x, y)，其中 x != y 但其他情况下是任意的。
如何在不重复有序对的情况下找到最长的链？
例如让
S = {(-1, 1.2), (4, 2), (1.2, 3), (3, 5.2), (4.2, -1), (5.2, 1), (3, 2)} .
最长链由 (-1, 1.2), (1.2, 3), (3, 5.2), (5.2, 1) 组成。
还有一条链 (-1, 1.2), (1.2, 3), (3, 2) 但不是最长的。
迭代整个集合是一种解决方案，但效率不高。
最佳答案
我不会编写代码。但这可能会对您有所帮助。
您必须了解图形算法。认为你的对是一个有输入端和输出端的节点。然后考虑您可以绘制的所有边缘。然后简化图表并使用一些最长路径搜索算法用于图表。 https://en.wikipedia.org/wiki/Longest_path_problem
关于c++ - 从一组有序对 (x, y) 中找到最长链的最有效算法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35007215/