332. Reconstruct Itinerary

題目網址：https://leetcode.cn/problems/reconstruct-itinerary/

題意：給一航線列表 tickets, 其中 tickets[i] = [from_i, to_i] 表示飛機出發和降落的地點。請你對該行程進行重新規劃排序。

所有這些機票都屬於一個從 JFK 出發的人, 所以該行程必須從 JFK 開始。如果存在多種有效的行程, 請你按字典排序返回最小的行程組合。

e.g. 行程 ["JFK", "LGA"] 與 ["JFK", "LGB"] 相比就更小, 排序會更靠前

假定所有機票至少存在一種合理的行程。所有的機票都必須使用, 且每張只能用一次

Solution：

首先考慮下面這張圖, 總共有兩條合法路徑：

JFK ➔ AAA ➔ JFK ➔ BBB ➔ JFK

JFK ➔ BBB ➔ JFK ➔ AAA ➔ JFK

由於要選擇字典順序最小的, 所以我們選擇第一條

要如何每次都先拜訪最小的鄰近 node, 並記錄重複的點
➔ 將 adj[v] 宣告成 multiset, 這樣 insert 到 adj[v] 的 node 就會自動由小到大排序, 且允許重複元素。因為有可能 v1 重複拜訪 v2 多次, 由於每張票都必須被使用, 故 adj[v1] 要重複紀錄 v2

考慮下面的特殊情形：

若先拜訪 AAA, 就沒辦法回到 JFK 了 ➔ 這樣就無法拜訪剩餘的邊

也就是說, 當我們 Greedy 拜訪順序最小的 node 時, 很可能會踏入「死路」導致無法遍歷所有的邊

因此, 我們利用 post order 倒著遍歷。若當前 node 不能繼續往下走, 則把它加到 res 中, 最後再將 res 反轉即可

想法：利用 Hierholzer 演算法 (DFS + post order)

從起點出發, 進行 DFS

當沿著邊 e 從某個 v1 移動到另外一個頂點 v2 時, 需要刪除 e (避免重複拜訪)

如果沒有可移動的路徑, 則將所在節點加入到 res 中, 並返回

反轉 res

下圖可以看到由 tickets 所建立的 tree, 對該 tree 取 post order 再反轉即為答案

cpp

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (const auto& [src, dst] ：tickets) {
            adj[src].emplace(dst);
        }

        vector<string> res;
        dfs("JFK", res);
        reverse(res.begin(), res.end());

        return res;
    }

private:
    // 用 multiset 是因為 adj[v] 的 node 會由小到大排序, 這樣就會先拜訪 string 順序較小的
    // 且有可能 v1 重複拜訪 v2 多次, 由於每張票都必須被使用, 故 adj[v1] 要重複紀錄 v2
    unordered_map<string, multiset<string>> adj; // adjacent list

    void dfs(const string& src, vector<string>& res){
        while (!adj[src].empty()) {
            const auto next = *adj[src].begin();
            adj[src].erase(adj[src].begin());
            dfs(next, res);
        }
        res.emplace_back(src);
    }
};

time： $O (E \cdot l o g (E))$ ➔ 從 multiset 中移除一條邊需花 $O (l o g (E))$ , 總共需移除 E 條
space： $O (V + E)$ ➔ adj