algo-aha

边的后序编号<=>逆欧拉路径。类似：点的后序编号=>逆拓扑排序。

把边加入visited[]数组<=>从图中删除边，这就有Hierholzer算法：删除出边再dfs递归，无边可删时把当前点输出到栈。

重构行程

• https://leetcode.com/problems/reconstruct-itinerary/

Hierholzer算法

vector<string> findItinerary(vector<vector<string>>& tickets) {
    // 已知欧拉路径存在且从JFK开始，一张机票一条边，求遍历所有边的欧拉路径
    // Hierholzer算法：删除出边再dfs递归，无边可删时把当前点输出到栈。 
    unordered_map<string, multiset<string>> adj;
    for (auto &ticket : tickets)
        adj[ticket[0]].insert(ticket[1]);
    
    vector<string> ans;
    dfs("JFK", adj, ans);
    reverse(ans.begin(), ans.end()); // 逆欧拉路径
    return ans;
}

void dfs(const string &from, unordered_map<string, multiset<string>> &adj, vector<string> &ans) {
    auto &tos = adj[from];
    while (!tos.empty()) {
        auto next = *tos.begin();
        tos.erase(tos.begin());
        dfs(next, adj, ans);
    }
    ans.push_back(from); // ans当栈用
}

开组合锁

• https://leetcode.com/problems/cracking-the-safe

正常使用visited[]数组

string crackSafe(int n, int k) {
    // 要求能覆盖全部密码组合，就是要找欧拉路径
    // 每个节点有k条出边和k条入边，入度==出度，一定有欧拉回路
    // n-1位数作为节点，边是 (后n-1位数)+any['0'..'k')，下一节点是边的后n-1位数
    // 边的后序遍历编号等于逆欧拉回路
    unordered_set<string> visited;
    string str(n, '0');
    visited.insert(str);

    string ans;
    function<void(const string &)> dfs = [&](const string &prefix) {
        for (int i = 0; i < k; i++) { // 遍历所有未访问的边
            string x = to_string(i);
            auto next = prefix + x;
            if (visited.count(next)) continue;
            visited.insert(next);

            dfs(next.substr(1));
            ans += x; // 后序遍历
        }
    };

    dfs(str.substr(1));
    ans += str; // 后序遍历
    reverse(begin(ans), end(ans)); // 逆欧拉路径
    return ans;
}