# 332. Reconstruct Itinerary

## 想法
在有向圖中找出字典序最小的歐拉路線，使用Hierholzer's algorithm
## 演算法

void dfs(u, adj, path):
    由小到大遍歷u的所有鄰居v:
        移除(u,v)
        dfs(v, adj, path)
    將u加入path中

main():
    將tickets轉為有向圖unorderedmap <string, multiset<string>> adj
    宣告字串陣列path
    dfs("JFK", adj, path)
    反轉path
    回傳path

## 程式碼

#include <bits/stdc++.h>
using namespace std;

class Solution {
    
public:
    void dfs(string u, unordered_map <string, multiset <string>> &adj, vector <string> &path) {
        while(!adj[u].empty()) {
            string v = *adj[u].begin(); 
            adj[u].erase(adj[u].begin());
            dfs(v, adj, path);
        }
        path.push_back(u);
    }
    
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map <string, multiset <string>> adj;
        for (int i = 0; i < tickets.size(); i++) {
            string u = tickets[i][0], v = tickets[i][1];
            adj[u].insert(v);
        }
        vector <string> path;
        dfs("JFK", adj, path);
        reverse(begin(path), end(path));
        return path;
    }
};

## 問題
1. 圖的點是字串，但adj的索引是數字，如何解決這個問題
> 用unordered_map將字串映射到字串陣列，這是一種特殊的鄰接串列
2. 每次都要知道字典序最小的是誰，如何解決這個問題
> 用set，set的特性是它會排序，不過這題是多重圖，所以用multiset
3. 這題是簡單圖還是多重圖
> 多重圖，如果把它當作簡單圖會錯，題目沒有明講是簡單圖建議一律當成多重圖處理
4. 為什麼在程式的第9行要用```adj[u].erase(adj[u].begin());```，而不是```adj[u].erase(v);```
> 因為這是multiset，如果使用```adj[u].erase(v);```，會移除多個同名節點，但我們的目的是要移除現在的這個就好，所以用```adj[u].erase(adj[u].begin());```
5. 為什麼```由小到大遍歷u的所有鄰居v:```要實作成```while(!adj[u].empty())```，而不是```for(auto it = begin(adj[u]); it != end(adj[u]); it++)```
> 因為迴圈內有移除集合元素，這樣會導致迭代發生錯誤