有约不来过夜半
闲敲棋子落灯花
图的深搜，这道题注意几个点：
- 不同的地点可能重复，所以邻接表的表项和判重应该都是行程下标
- 一开始进行排序，后面就不用考虑字符串比较了
邻接表还是用哈希表吧。
class Solution {
private:
static bool cmp(vector<string> &a, vector<string> &b) {
if (a[0] == b[0]) return a[1] < b[1];
else return a[0] < b[0];
}
bool dfs(string curr, unordered_map<string, vector<int>> &g, vector<bool> &vis, vector<string> &ans, int cnt, const vector<vector<string>> &tickets) {
ans.push_back(curr);
if (cnt == 0) return true;
for (int edge_index : g[curr]) {
if (!vis[edge_index]) {
vis[edge_index] = true;
if (dfs(tickets[edge_index][1], g, vis, ans, cnt - 1, tickets))
return true;
vis[edge_index] = false;
}
}
ans.pop_back();
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
sort(tickets.begin(), tickets.end(), cmp);
unordered_map<string, vector<int>> g;
vector<string> ans;
vector<bool> vis(tickets.size());
for (int i = 0; i < tickets.size(); i++) {
g[tickets[i][0]].emplace_back(i);
}
dfs("JFK", g, vis, ans, tickets.size(), tickets);
return ans;
}
};
