題目: 2097. Valid Arrangement of Pairs
難度: Hard
目前下列解法的時間複雜度: O(n) ，（用到 unordered_map ，把 O(lg(n)) 壓成 O(1) ，於是 O(n*lg(n)) 變成 O(1) ）
題目說明
（原題意）
給定一長度 n 的 0-indexed 的陣列，內含一堆 (左端,右端) 的 pair ，求使得「對於每個整數 i ，1 <= i < 陣列長度，第 i-1 個 pair 的右端等於第 i 個 pair 的左端」的排列，回傳排列後的樣子。
題目保證能夠排出來。
題目保證一陣列中沒有相同的 pair 。
例如：
（單鍊無分岔）
Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
（有環無分岔）
Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
（有環有分岔）
Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
（轉換後題意）
給定一有向圖，請給出 邊一筆畫 依序要經過的邊。邊要以 (起點,終點) 的方式給出。
題目保證能一筆畫。
題目保證沒有重邊。（無重複的有向邊，但有可能兩個點有雙向邊各一條。）
解法：拔拔樂（把邊刪掉）
0. 理解出每個 pair 其實就是有向邊，自左端「離開」並「進入」右端。整個陣列是一張圖。
1. 回憶高中數研社教的，可以知道要達成 邊一筆畫 ，需要：
a. 先假設你能 邊一筆畫 。
b. 當你能一筆畫時，除了起點和終點之外，「進入」一個點的次數等於「離開」一個點的次數。
c. 若起點不等於終點，即頭尾不能相連，則起點的「進入」次數較「離開」次數少1；終點的「離開」次數較「進入」次數少1。
d. 條件不符時不能一筆畫。
2. 抓起點，即「進入」次數較「離開」次數少1者。若無，則代表為頭尾相連，則任意點皆可。
3. 紀錄從每個點「離開」的邊有哪些。
4. recurrsion 的方式，從起點開始，一個一個點走到不能再走。紀錄起點邊及走過前一個邊後的下一個邊要選誰。用過的邊都刪掉。
5. 處理環。 recurrsion 處理完該點之後的路徑後，若離開的邊還有剩，則代表該點可以自己建一個環（「進入」一個點的次數等於「離開」一個點的次數）。看一下還有沒有剩下的邊沒用掉，有的話就做個環。
6. 透過記錄到的起點邊，逐步查詢「下一個邊要選誰」，將遇到的邊都加進回傳值中。
7. 好了。
source code
一些技巧：
0. 避免濫用 unordered_map / unordered_set
1. 當一條邊被走過，就把他刪了。
2. 因為岔路選擇的順序沒什麼關係（recursion時會把岔路環），可以用 unordered_map<int,vector<int> > 存每個點「離開」的邊有哪些，用過的邊直接 vector::pop_back 即可。
3. n 條邊，經過的點數 = n+1，每條邊：
a. 在計算進出次數時4次（平均 O(1) ）（ unordered_map::[] ）。
b. 找起點 O(1) （ unordered_map::iterator ）。
c. recursion時，總計被搜尋一次（平均 O(1) ）（ unordered_map::[] ）、總計被刪除一次（ O(1) ）（ vector::pop_back ）、記錄下一條邊是誰（ O(1) ） 。
d. recursion後，依據紀錄建立回傳值（ O(1) ）。
=> O(1)*8*n = O(n)
到底為什麼比賽中寫不出來，我明明在高中就會手動解邊一筆畫問題
打完疫苗累爆還去打比賽，我是不是瘋了
單手打code
難度: Hard
目前下列解法的時間複雜度: O(n) ，（用到 unordered_map ，把 O(lg(n)) 壓成 O(1) ，於是 O(n*lg(n)) 變成 O(1) ）
題目說明
（原題意）
給定一長度 n 的 0-indexed 的陣列，內含一堆 (左端,右端) 的 pair ，求使得「對於每個整數 i ，1 <= i < 陣列長度，第 i-1 個 pair 的右端等於第 i 個 pair 的左端」的排列，回傳排列後的樣子。
題目保證能夠排出來。
題目保證一陣列中沒有相同的 pair 。
例如：
（單鍊無分岔）
Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
（有環無分岔）
Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
（有環有分岔）
Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
（轉換後題意）
給定一有向圖，請給出 邊一筆畫 依序要經過的邊。邊要以 (起點,終點) 的方式給出。
題目保證能一筆畫。
題目保證沒有重邊。（無重複的有向邊，但有可能兩個點有雙向邊各一條。）
解法：拔拔樂（把邊刪掉）
0. 理解出每個 pair 其實就是有向邊，自左端「離開」並「進入」右端。整個陣列是一張圖。
1. 回憶高中數研社教的，可以知道要達成 邊一筆畫 ，需要：
a. 先假設你能 邊一筆畫 。
b. 當你能一筆畫時，除了起點和終點之外，「進入」一個點的次數等於「離開」一個點的次數。
c. 若起點不等於終點，即頭尾不能相連，則起點的「進入」次數較「離開」次數少1；終點的「離開」次數較「進入」次數少1。
d. 條件不符時不能一筆畫。
2. 抓起點，即「進入」次數較「離開」次數少1者。若無，則代表為頭尾相連，則任意點皆可。
3. 紀錄從每個點「離開」的邊有哪些。
4. recurrsion 的方式，從起點開始，一個一個點走到不能再走。紀錄起點邊及走過前一個邊後的下一個邊要選誰。用過的邊都刪掉。
5. 處理環。 recurrsion 處理完該點之後的路徑後，若離開的邊還有剩，則代表該點可以自己建一個環（「進入」一個點的次數等於「離開」一個點的次數）。看一下還有沒有剩下的邊沒用掉，有的話就做個環。
6. 透過記錄到的起點邊，逐步查詢「下一個邊要選誰」，將遇到的邊都加進回傳值中。
7. 好了。
source code
一些技巧：
0. 避免濫用 unordered_map / unordered_set
1. 當一條邊被走過，就把他刪了。
2. 因為岔路選擇的順序沒什麼關係（recursion時會把岔路環），可以用 unordered_map<int,vector<int> > 存每個點「離開」的邊有哪些，用過的邊直接 vector::pop_back 即可。
3. n 條邊，經過的點數 = n+1，每條邊：
a. 在計算進出次數時4次（平均 O(1) ）（ unordered_map::[] ）。
b. 找起點 O(1) （ unordered_map::iterator ）。
c. recursion時，總計被搜尋一次（平均 O(1) ）（ unordered_map::[] ）、總計被刪除一次（ O(1) ）（ vector::pop_back ）、記錄下一條邊是誰（ O(1) ） 。
d. recursion後，依據紀錄建立回傳值（ O(1) ）。
=> O(1)*8*n = O(n)
