跳到主要内容

LeetCode 332. 重新安排行程

本节目标

用逆序邻接表和后序收集构造字典序最小的完整行程。

这是图论综合中“每条边都必须恰好用一次”的母题。每张机票是一条有向边，行程固定从 JFK 出发，还要求在可行答案中取字典序最小者。

查看 LeetCode 原题

题意与约束​

tickets[i] = [from, to] 是一张独立机票；相同机场对可多次出现，仍是不同的边。返回依次经过的机场，必须从 JFK 出发、使用每张机票恰好一次，结果长度恰好为机票数加一，并在可行行程中取字典序最小者。

直接思路与瓶颈​

从 JFK 每次贪心选最小目的地可能过早走进死路，回溯枚举所有机票排列又会随机票数爆炸。题目保证存在解，因此可以在消耗边的 DFS 中延后写入节点：先走完能走的票，再把机场后序加入答案。

图模型与算法推导​

建立 from -> destinations 邻接表，每个列表逆序排序，从尾部弹出即以 O(1) 取得当前字典序最小目的地。DFS 到 airport 时不断弹出一张未用机票到 nxt 并递归；直到该机场无边可用才把它放入 route。结束后反转后序序列。

正确性依据​

每次弹出一张机票后该边立即从邻接表删除，故每张票至多使用一次；DFS 持续到没有边可走才后序记录，所有被消耗的边都会被拼入同一条完整行程。当前可选边按字典序最小取出；若需回到分叉点，后序收集会把暂未闭合的部分放到正确位置，因此反转后得到题目保证存在的字典序最小完整行程。

样例执行过程​

对 [['JFK','KUL'],['JFK','NRT'],['NRT','JFK']]，JFK 的逆序列表为 [NRT,KUL]，先从尾部取 KUL，无后继则后序加入 KUL；回到 JFK 后取 NRT -> JFK，此时 JFK 已无边，依次后序加入 JFK,NRT,JFK。收集序列为 [KUL,JFK,NRT,JFK]，反转为 [JFK,NRT,JFK,KUL]，而非局部贪心的死路。

代码实现​

C++17
#include <algorithm>
#include <map>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        graph.clear();
        route.clear();
        for (const auto& ticket : tickets) {
            graph[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [airport, destinations] : graph) {
            sort(destinations.rbegin(), destinations.rend());
        }

        dfs("JFK");
        reverse(route.begin(), route.end());
        return route;
    }

private:
    map<string, vector<string>> graph;
    vector<string> route;

    void dfs(const string& airport) {
        while (!graph[airport].empty()) {
            string nxt = graph[airport].back();
            graph[airport].pop_back();
            dfs(nxt);
        }
        route.push_back(airport);
    }
};

复杂度分析​

设机票数为 m。全部邻接表排序总计 O(m log m)，DFS 每张机票只弹出一次为 O(m)；邻接表、递归栈和行程使用 O(m) 空间。

边界与易错点​

  • 逆序排序后从尾部取值，才同时满足字典序和高效删除。
  • 不能刚到达机场就写入答案，必须在边耗尽后后序加入。
  • 相同 [from,to] 机票不能去重。
  • 只讲本题的构造过程，不扩展完整欧拉图判定理论。

模式迁移​

当任务要求逐条消耗连接，并按回溯完成顺序拼接结果时，可用“取边递归、后序入答案、最终反转”；局部选择规则由邻接表排序承载。