主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始數的二維整數陣列 pairs，其中 pairs[i] = [starti, endi]。一個 pairs 的排列是「合法的」，代表著對於每一個滿足 1 ≦ i < pairs.length 的索引值 i，endi-1 == starti 都成立。
回傳任意一個 pairs 的合法排列。
注： 測資之生成保證存在至少一個 pairs 的合法排列。
限制：
1 ≦ pairs.length ≦ 10 ^ 5
pairs[i].length == 2
0 ≦ starti, endi ≦ 10 ^ 9
starti != endi
沒有兩個數對完全一致。
存在至少一個 pairs 的合法排列。
範例測資：
範例 1：
輸入： pairs = [[5,1],[4,5],[11,9],[9,4]]
輸出： [[11,9],[9,4],[4,5],[5,1]]
解釋：
此排列是合法的，因為每一個 endi-1 都等於 starti。
end0 = 9 == 9 = start1
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
範例 2：
輸入： pairs = [[1,3],[3,2],[2,1]]
輸出： [[1,3],[3,2],[2,1]]
解釋：
此排列是合法的，因為每一個 endi-1 都等於 starti。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
[[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 之排列也是合法的。
範例 3：
輸入： pairs = [[1,2],[1,3],[2,1]]
輸出： [[1,2],[2,1],[1,3]]
解釋：
此排列是合法的，因為每一個 endi-1 都等於 starti。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
解題思維：
首先觀察一下合法排列的「長相」。
以範例測資一的答案為例：[[11,9],[9,4],[4,5],[5,1]]，把中括號刪光光之後會得到 11 9 9 4 4 5 5 1。
可以看到除了開頭和結尾的兩個數字以外的其他在中間的數字都是兩兩一組相同。因此不如就每兩個數字省略掉其中一個。所以上面的答案會變成 11 9 4 5 1。
而這可以解讀成從數字 11 走到 9、再走到 4、其次是 4、再來是 5、最後是 1。而可以看到其中如「11 走到 9」對應著原本的 [11,9] 之數對。
因此我們可以把輸入視為是數線上各個數字（只考慮有出現在 pairs 中的）作為頂點，然後以 pairs 作為整張圖的邊（注意，這些邊是「有向」的）。
而從題意可以得到，我們要在圖中找出「一筆劃走完所有邊」的路徑。以前在這題有提過一筆劃存在性的充分必要條件，但那個適用的是無向圖的情況。不過有向圖實際上還是類似，只是現在有邊本身有 in-degree（入邊）和 out-degree（出邊）之差別。
因此對於有向圖來說，一筆劃存在若且唯若
（一）「每一個頂點的出邊數等於入邊數」
或是
（二）「存在恰好一個頂點滿足出邊數減去入邊數等於 1，且存在恰好另一個頂點滿足出邊數減去入邊數等於 -1」
（以下用（一）和（二）代稱這兩個條件）
（實際上還有一個前置條件——這個有向圖必須至少是弱連通（Weakly Connected）的，也就是說將所有邊視為無向之後此圖是連通無向圖。不過這個條件通常會被無視，因為絕大部分時候都已經假設是弱連通有向圖了）
不過一筆劃實際上有兩種分類——一種是歐拉路徑（Eulerian Path）和歐拉迴路（Eulerian Circuit），前者是起點和終點不一定要同一個點，且（一）或（二）滿足時都可以找到；後者是起點和終點必定要是同一個點，且只有（一）滿足時才能找到。
而根據題意以及我們生成的圖之特性，題目必定會滿足（一）或是（二）其中一個，但不保證是其中哪一個。而（二）可以多加一條邊在滿足條件的這兩個點之間來變成（一）。所以我們可以先討論如何解決（一）。
有一種演算法叫做 Hierholzer's Algorithm，其精神如下：
既然給定的圖滿足（一），那隨便從任何一點開始都可以。稱其為 v。
可以看到一旦從 v 走出去之後便會「破壞」（一）的條件，此時 v 的入邊比出邊多 1。而因此如果從 v 一直走一直走（無論經過的點之前有沒有出現過），走到走不動為止。此時停留點必定會是 v 本身。原因正是因為其他所有的點此時都還滿足（一），一旦走進某個點（消耗它的入邊數）必定可以走出去（消耗它的出邊數）。唯獨 v 因為最一開始走出去的行為而「多消耗了」一次出邊數。
此時可以得到一個迴路。但這個迴路不一定有經過所有的邊。因此如果現在這個迴路上有點 v' 存在使得還有「沒有使用過」的邊存在的話，則我們可以用 v' 作為「新的 v 點」然後重複以上步驟（當然，是走那些還沒走過的邊）。
所以會得到舊的迴路 A 和新的迴路 B，而只要將 A 上的 v' 替換成整個 B 即可將兩個迴路合併成單一一個。
即假設 A 是 v → …… → v' → …… → v 、 B 是 v' → a → …… → b → v'，則合併後會是
v → …… → (v' → a → …… → b → v') → …… → v
重複這個找 v' 點的動作直到所有邊都被使用過為止。
而因為圖是弱連通圖（還記得那個「隱藏的」前置條件嗎？），這必定可以使用掉所有的邊。因此最後合併出來的迴路即為歐拉迴路。
如果上面的直覺說明不夠說服讀者的話。基本上上面的敘述的正確性可以由證明「某一個點被『走過』兩次以上的迴路，可以從該點拆成多個子迴路」、「兩個迴路交於至少一點，可以合併成一個迴路」、「弱連通的特性保證整個過程可以看過所有邊」即可完成。因為我懶，所以在此省略。
話雖如此，實際上要怎麼實作呢？
首先，我們需要存邊的資訊。用鄰接表（Adjacency List）即可（參見這題）。不過因為我們需要紀錄每一個點哪些邊用過了，所以鄰接表還要加上一些額外的資訊。由於通常是用大小可變的陣列來實作鄰接表（例如說 C++ 的 vector）。而正因為是陣列，因此直接每一個點用一個變數紀錄現在看到哪一條邊即可。這樣一來每一個點不用每一次都重新掃過它的所有邊。
接著是觀察迴路的特性。假設我們從隨便一點 v 一直走到不能走後回到 v，得到了 v → v' → v 這個迴路（這邊先不假設是用什麼資料結構紀錄這個迴路，先叫它 S）。然後再假設這邊的 v' 跟上面的例子一樣有 v' → a → …… → b → v' 這個迴路。
可以看到結尾的那個 v 確定不會再跟其他迴路合併了，因此可以安心地寫一個 v 在某處紀錄最後整個歐拉迴路的結果（一樣，先不假定其資料結構。先稱其為 V）。所以此時 S = v → v' 、 V = v。
S 現在最後一個元素是 v'，則此時我們會根據 v' 在鄰接表中還有沒有走過的邊。因此一樣繼續從 v' 走到不能走為止，然後得到了 v' → a → …… → b → v' 這個迴路。而因為是從 v'「長」出來的，所以此時 S = v → v' → a → …… → b → v'。
而跟前面的結尾 v 同理，此時 S 結尾的 v' 也把邊掃完了。因此可以安心地寫下 v' 到結果中，此時 V = v v' 且 S = v → v' → a → …… → b。
然後從 b 開始以此類推。
最後 S 會變成空的，而 V 會變成 v v' b …… a v' v。
此時的 V 就是所求的歐拉迴路。不過可以看到上面過程中是直接把新的元素丟到 V 的結果，因此實際上這個迴路跟預期的會「相反」。
因此可以直接使用一個支援前後都可以插入或刪除元素的資料結構，例如說雙端佇列（Deque），然後把新的元素放在「前面」。又或是說用普通的動態陣列把迴路反序存著，最後再整個反轉。抑或者是在當初建立鄰接表時，把邊的方向先反轉。這樣子用動態陣列存結果的時候不需要額外反轉一次。
方式族繁不及備載。範例程式碼中是採取 S 用堆疊（Stack）實作（因為從上面可以看到每次是拿結尾的點；不過同樣論述可以應用開頭的點，所以其他資料結構也可行）然後 V 是一個動態陣列並採取將圖上的邊方向反轉的策略。
不過上面講述的是（一）的情況。（二）雖然加個邊便可以直接套用上面的方式做，但那個加上去的邊終究是假的。因此最後移除掉把元素挪位一下即可得到一個歐拉路徑。
例如說在範例測資一中，我們會多加一條邊從 1 走到 11。因此會得到歐拉迴路 4 5 1 11 9 4（注意到上面的演算法會是隨便取最一開始點，所以可能會長得不一樣）。由於 1 到 11 是假的邊，因此將這個迴路從那邊斷開得到 4 5 1 和 11 9 4 兩個路徑。
把右邊的路徑擺在後面、左邊的路徑擺在前面並將那個重複出現的 4 刪掉其中一個便可以得到 11 9 4 5 1。
但最後的最後，不要忘記題目所求不是上面求出來的歐拉迴路或歐拉路徑。那些走過的「邊」才是我們要的東西。
因此回到範例測資一然後跑過上面的演算法會得到 11 9 4 5 1 這個路徑，而每兩個數字代表著原本 pairs 中的一個數對，即 [11, 9] 、 [9, 4] 、 [4, 5] 、 [5, 1]。
所以最後再掃過一次歐拉路徑或迴路，便可以重建出原本要的 pairs 之合法排列，即所求。
而時間複雜度是「建立鄰接表」+「Hierholzer's Algorithm 之實作」+「重建答案」。
令E 為圖中的邊數（每一條邊即是一個 pairs 中的數對，因此 E 恰好是 pairs.length）、 V 是圖中的點數（即 pairs 中有多少種數字，可以看到最多只會有 2E 個；而下界為 O(sqrt(E)) 個，因為題目限制有說到不會有兩個數對長一模一樣。其中 sqrt(E) 是 E 的平方根）
「Hierholzer's Algorithm 之實作」因為有用額外的變數紀錄每一個點看哪些邊。因此每一個邊最多被看一次。所以這邊的時間是 O(E)。
「重建答案」只是單純地掃過一次歐拉路徑或迴路，因此時間是 O(E)。
至於「建立鄰接表」則因為數值本身與 V 、 E 無關。根據本題的數值範圍，不可能直接開與其範圍大小相符的陣列。故這些數值需要「重新編號」（Re-indexing）。而這可以用雜湊表（Hash Table）來做到，也可以把所有數值排序並按照大小順序重新編號。前者「實務上」雖然會因為雜湊碰撞次數不多而得到單次操作平均 O(1)，但最糟可以到 O(V)；後者因為要排序，所以會是 O(V log V)（雖然可以改用例如說基數排序法（Radix Sort）等非比較排序法，但時間複雜度的表示法中會包含數值範圍本身。所以這邊怕各種討論的麻煩而忽略）。
因此最終時間複雜度會是 (平均 O(V) 的雜湊或是 O(V log V) 的排序) + O(E) + O(E)，即平均 O(E) 或是 O(E log E)。
題外話：這篇心得好長。跟我預期的不太一樣 XD
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
