歐拉迴路

332. Reconstruct Itinerary

753. Cracking the Safe

歐拉迴路：一筆畫不重複地遍歷所有的邊回到原點

哈密爾頓迴路：遍歷所有的點有且僅有一次回到原點

技巧：

1. 根據點遍歷鄰邊時，遇到無法前進的點時回退保存遍歷的邊，即是逆序的保存遍歷路徑
2. n維的de Bruijn序列圖上找哈密爾頓迴路 = n-1維的de Bruijn序列圖上找歐拉迴路

332. Reconstruct Itinerary

class Solution { map<string, multiset<string>> neighbors; vector<string> res;public: vector<string> findItinerary(vector<pair<string, string>> tickets) { for (auto ticket: tickets) neighbors[ticket.first].insert(ticket.second); dfs("JFK"); reverse(res.begin(), res.end()); return res; } void dfs(string cur) { while (neighbors[cur].size()) { string neighbor = *neighbors[cur].begin(); neighbors[cur].erase(neighbors[cur].begin()); dfs(neighbor); } res.push_back(cur); }};

753. Cracking the Safe

class Solution {public: string crackSafe(int n, int k) { int v = pow(k, n-1); vector<int> visited(v * k, 0); string s(n-1, 0), res; dfs(0, v, k, visited, res); res += s; return res; } void dfs(int u, int v, int k, vector<int>& visited, string& s) { for (int i=0; i<k; i++) if (!visited[u*k+i]) { visited[u*k+i] = 1; dfs((u*k+i)%v, v, k, visited, s); s += to_string(i); } }};

推薦閱讀：