单程航班问题

让我们暂时忘记数据结构和图表。

首先，我需要指出每个人都假设没有循环。如果路线经过一个机场两次，那么这将是一个更大的问题。

---

但是现在让我们保持这个假设。

实际上，输入数据已经是一个有序集合了。每张机票都是引入一组机场顺序的关系的元素。(英语不是我的母语，所以这些可能不是正确的数学术语)

每张机票都包含像这样的信息：机场X < 机场Y，因此在通过机票的一次遍历时，算法可以从任何机场开始重新创建一个有序列表。

---

现在让我们放弃“线性假设”。这种东西中不能定义任何顺序关系。输入数据必须被视为正式语法的产生规则，其中语法词汇集是机场名称的集合。像这样的票：

src: A
dst: B

实际上是一对产生式：

A->AB
B->AB

从中你只能保留一个。

现在你必须生成每个可能的句子，但是你只能使用每个产生式一次。使用每个产生式仅一次的最长句子是正确的解决方案。

最简单的方法是使用哈希表，但这并不具有最佳的最坏情况复杂度(O(n²))

相反:

1. 创建一堆包含(src, dst)的节点 O(n)
2. 将节点添加到列表中并按src排序 O(n log n)
3. 对于每个(目标)节点，在列表中搜索相应的(源)节点 O(n log n)
4. 找到起始节点(例如，使用拓扑排序或在步骤3中标记节点) O(n)

总体而言: O(n log n)

(对于这两种算法，我们假设字符串的长度可以忽略不计，即比较是O(1))

不需要哈希或类似的东西。 这里真正的输入大小不一定是票数（比如说n），而是票的总“大小”（比如说N），也就是编码它们所需的char的总数。

如果我们有一个包含k个字符的字母表（这里k大约为42），我们可以使用桶排序技术对一个由n个字符串组成、总大小为N、并使用包含k个字符的字母表进行编码的数组进行排序，时间复杂度为O(n + N + k)。如果n <= N（显然）且k <= N（嗯，N是十亿级别的，不是吗？）则以下内容有效。

1. 按照给定的顺序，从机票中提取所有机场代码，并将它们存储在一个结构体中，该结构体具有代码作为字符串和票号作为数字。
2. 根据它们的代码对这个结构体数组进行桶排序。
3. 遍历排序后的数组，并为每个新遇到的航空公司代码分配一个序数（从0开始）。对于所有具有相同代码的元素（它们是连续的），转到票（我们已经用代码存储了编号）并更改票的代码（选择正确的src或dst）为序数。
4. 在这次遍历数组时，我们可能会确定原始源src0。
5. 现在所有的机票都已经被重写为序数，可以将它们解释为以src0为起点的列表。
6. 对机票进行列表排名（保持距离从src0的拓扑排序）。

如果您假设一个可连接的列表结构，可以存储所有内容（可能在磁盘上）：

1. 创建2个空哈希表S和D
2. 获取第一个元素
3. 在D中查找其src
4. 如果找到，则从D中删除相关节点并将其链接到当前节点
5. 如果未找到，则将节点插入到以src为键的S中
6. 反向从3开始重复，src<->des，S<->D
7. 使用下一个节点从2开始重复。

O(n)时间。至于空间，birthday paradox（或类似的东西）将使您的数据集比完整集合小得多。在不幸的情况下，即使最坏情况是O(n)，您也可以从哈希表中驱逐随机运行，并将它们插入到处理队列的末尾。您的速度可能会变慢，但只要您能远远超过期望碰撞的阈值（~O(sqrt(n))），您应该期望定期缩小数据集（表和输入队列的组合）。

我认为这里采用基于图形的方法。

每个机场是一个节点，每张票是一条边。暂时让每条边都是无向边。

在第一阶段中，您正在构建图形：对于每张票，您查找源和目的地，并在它们之间建立一条边。

现在图已经构建完成，我们知道它是非循环的，并且只有一条路径通过它。毕竟，您只有旅行的机票，而且从未到过相同的机场。

在第二个阶段中，您正在搜索图形：选择任何一个节点，并启动两个方向的搜索，直到您发现无法继续为止。这些是您的源和目的地。

如果您需要明确说明哪个是源，哪个是目的地，请为每条边添加一个目录属性（但仍然保持无向图）。一旦您确定了候选源和目的地，您可以根据与它们相连的边来判断哪个是哪个。

这个算法的复杂度取决于查找特定节点所需的时间。如果您能实现O(1)，那么时间应该是线性的。您有n张票，因此构建图需要O(N)步骤，然后搜索需要O(N)，重构路径需要O(N)。仍然是O(N)。邻接矩阵将为您提供此功能。

如果您无法节省空间，可以对节点进行哈希，这将在最佳哈希和所有垃圾下为您提供O(1)。

请注意，如果任务仅是确定源和目的地机场（而不是重构整个行程），那么这个谜题可能会变得更有趣。
也就是说，假设机场代码以整数形式给出，则可以使用数据的O（1）次遍历和O（1）个附加内存来确定源和目的地机场（即不需要使用哈希表、排序、二分查找等）。
当然，一旦找到源，索引和遍历整个路线也变得微不足道，但从那时起，整个过程将需要至少O（n）个额外的内存（除非您可以原地对数据进行排序，顺便说一句，这样可以在O（n log n）时间内解决原始任务，并且只需要O（1）个额外的内存）。

前提条件

首先，创建一些包含您路线的部分的子旅行结构。

例如，如果您的完整旅程是 a-b-c-d-e-f-g，则子旅行可以是 b-c-d，即您旅程的连接子路径。

现在，创建两个哈希表，将城市映射到包含该城市的子旅行结构。因此，一个哈希表代表子旅行起始的城市，另一个哈希表代表子旅行结束的城市。这意味着，一个城市最多只能出现在其中一个哈希表中。

正如我们后来将看到的那样，并不需要存储每个城市，而只需要存储每个子旅行的开头和结尾。

构建子旅行

现在，一个接一个地拿取车票。我们假设车票从x到y(表示为(x,y))。检查x是否是某个子旅程s的结尾（由于每个城市仅被访问一次，因此它不能已经是另一个子旅程的结尾）。如果x是起点，只需将当前车票(x,y)添加到子旅程s的末尾即可。如果没有以x结尾的子旅程，请检查是否存在以y开头的子旅程t。如果有，将(x,y)添加到t的开头。如果也没有这样的子旅程t，则创建一个包含(x,y)的新子旅程。

处理子旅程应使用一些特殊的"技巧"。

• 创建一个包含(x,y)的新子行程s，应该将x添加到“子行程起始城市”的哈希表中，并将y添加到“子行程结束城市”的哈希表中。
• 在子行程s=(y,...)的开头添加一个新的票(x,y)，应该从起始城市的哈希表中移除y，并将x添加到起始城市的哈希表中。
• 在子行程s=(...,x)的末尾添加一个新的票(x,y)，应该从结束城市的哈希表中移除x，并将y添加到结束城市的哈希表中。

通过这种结构，与某个城市对应的子行程可以在摊销O(1)的时间内完成。

完成所有票务后，我们会得到一些子行程。请注意，在此过程之后，我们最多有(n-1)/2 = O(n)个这样的子行程。

连接子行程

现在，我们只是一个接一个地考虑子旅行。如果我们有一个子旅行s=(x,...,y)，我们只需要查看我们的结束城市哈希表，看看是否有以x结尾的子旅行t=(...,x)。如果有，我们将t和s连接成一个新的子旅行。如果没有，我们知道s是我们的第一个子旅行；然后，我们查看是否有另一个以y开头的子旅行u=(y,...)。如果有，我们将s和u连接起来。我们一直这样做，直到只剩下一个子旅行（这个子旅行就是我们整个原始旅行）。
我希望我没有忽略什么，但这个算法应该运行在：

• 构建所有子旅程（最多O(n)）可以在O(n)内完成，如果我们实现将机票添加到子旅程中的O(1)。如果我们有一些漂亮的指针结构或类似于此的东西（将子旅程实现为链接列表），那么这应该不是问题。同时，在哈希表中更改两个值是（平摊）O(1)。因此，这个阶段需要O(n)的时间。
• 连接子旅程直到只剩下一个也可以在O(n)内完成。要看到这一点，我们只需要看第二阶段所做的事情：哈希表查找，需要平摊O(1)和使用指针连接等可以在O(1)内完成的子旅程连接。

因此，整个算法的时间复杂度为O(n)，这可能是最优的O界限，因为至少每张机票都需要被查看。

我在这里提供了一个更通用的解决方案：

您可以在同一机场停留多次，但必须恰好使用每张机票1次

您可以为旅程的每个部分拥有多张机票。

每张机票都包含源和目的地机场。

您拥有的所有机票都是随机排序的。

您忘记了最初的出发机场（第一个源）和您的目的地（最后一个目的地）。

我的方法返回包含所有指定城市的城市列表（向量），如果存在这样的链，则返回该列表为空。当有多种旅行方式时，该方法返回字典序最小的列表。

#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>

using namespace std;

struct StringPairHash
{
    size_t operator()(const pair<string, string> &p) const {
        return hash<string>()(p.first) ^ hash<string>()(p.second);
    }
};

void calcItineraryRec(const multimap<string, string> &cities, string start,
    vector<string> &itinerary, vector<string> &res,
    unordered_set<pair<string, string>, StringPairHash> &visited, bool &found)
{
    if (visited.size() == cities.size()) {
        found = true;
        res = itinerary;
        return;
    }
    if (!found) {
        auto pos = cities.equal_range(start);
        for (auto p = pos.first; p != pos.second; ++p) {
            if (visited.find({ *p }) == visited.end()) {
                visited.insert({ *p });
                itinerary.push_back(p->second);
                calcItineraryRec(cities, p->second, itinerary, res, visited, found);
                itinerary.pop_back();
                visited.erase({ *p });
            }
        }
    }
}

vector<string> calcItinerary(vector<pair<string, string>> &citiesPairs)
{
    if (citiesPairs.size() < 1)
        return {};

    multimap<string, string> cities;
    set<string> uniqueCities;
    for (auto entry : citiesPairs) {
        cities.insert({ entry });
        uniqueCities.insert(entry.first);
        uniqueCities.insert(entry.second);
    }

    for (const auto &startCity : uniqueCities) {
        vector<string> itinerary;
        itinerary.push_back(startCity);
        unordered_set<pair<string, string>, StringPairHash> visited;
        bool found = false;
        vector<string> res;
        calcItineraryRec(cities, startCity, itinerary, res, visited, found);
        if (res.size() - 1 == cities.size())
            return res;
    }
    return {};
}

这里是一个使用示例：

    int main()
    {
        vector<pair<string, string>> cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"Y", "W"}, {"W", "Y"}};
        vector<string> itinerary = calcItinerary(cities); // { "W", "X", "Y", "W", "Y", "Z" }
        // another route is possible {W Y W X Y Z}, but the route above is lexicographically smaller.

        cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"W", "Y"} };
        itinerary = calcItinerary(cities);  // empty, no way to travel all cities using each ticket exactly one time
    }