leetcode

0 class Solution {

1 vector<string> res;

2 int n;

3

4 typedef unordered_map<string, map<string, int>> adj_t;

5 bool rec(adj_t &adj) {

6 if (res.size() == n) return true;

7

8 const string &name = res.back();

9 for (auto &next : adj[name]) {

10 if (!next.second) continue;

11 res.push_back(next.first);

12 next.second--;

13 if (rec(adj)) return true;

14 next.second++;

15 res.pop_back();

16 }

17 return false;

18 }

19

20 public:

21 vector<string> findItinerary(const vector<vector<string>> &tickets) {

22 adj_t adj;

23

24 n = tickets.size() + 1;

25 for (const auto &ticket : tickets)

26 adj[ticket[0]][ticket[1]]++;

27

28 res = {"JFK"};

29 rec(adj);

30 return res;

31 }

32 };