https://leetcode.cn/problems/reconstruct-itinerary/description/

本质还是模板题，难点在于如何管理机票

<aside> 💡

输入前的预处理：

• map<string, vector<string>> mp
  • 用于管理所有机票
  • <from, toList>
  • toList经过排序，所以回溯过程中收集到的第一个解就是字节序最小的解
• map<string, vector<bool>> used
  • 与mp相对应，每张机票都对应一个bool

回溯三部曲：

• 参数：
  • string from：出发的机场
  • map<string, vector<string>> mp：使用map管理所有机票<from, toList>
• 终止条件：
  • 当前行程长度等于总行程长度时说明行程已经组织完毕
• 单层逻辑：
  • 通过mp获取当前from的所有to
  • 获取当前from的used数组
  • 遍历toList:
    • 跳过已经使用的机票
    • 递归：以当前to作为下一轮递归的from，进入递归
    • 回溯
    • 树层去重 </aside>

map<string, vector<bool>> used;
int totalItinerary;
vector<string> cur;
vector<string> ans;

void backtracking(const string& from, map<string, vector<string>>& mp) {
    if (!ans.empty()) {
        return;
    }
    if (cur.size() == totalItinerary) {
        ans = cur;
        return;
    }

    const vector<string>& toList = mp[from];
    vector<bool>& usedFrom = used[from];
    for (int i = 0; i < toList.size(); ++i) {
        // 跳过已经使用过的机票
        if (i < toList.size() && usedFrom[i]) {
            continue;
        }
        // 回溯
        usedFrom[i] = true;
        cur.push_back(toList[i]);
        backtracking(toList[i], mp);
        cur.pop_back();
        usedFrom[i] = false;

        // 树层去重
        while (i + 1 < toList.size() && toList[i + 1] == toList[i]) {
            ++i;
        }
    }
}

vector<string> findItinerary(vector<vector<string>>& tickets) {
    // 行程的长度
    totalItinerary = tickets.size() + 1;
    // 使用map管理机票，<from, toList>
    map<string, vector<string>> mp;
    for (auto& v : tickets) {
        mp[v[0]].push_back(v[1]);
    }
    for (auto& item : mp) {
        // 排序+构建used数组
        std::sort(item.second.begin(), item.second.end());
        used[item.first] = vector<bool>(item.second.size(), false);
    }

    cur.push_back("JFK");
    backtracking("JFK", mp);

    return ans;
}