本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中，我不僅會(huì)講解多種解題思路及其優(yōu)化，還會(huì)用多種編程語言實(shí)現(xiàn)題解，涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng)，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

給你一個(gè)下標(biāo)從?0?開始的二維整數(shù)數(shù)組?pairs?，其中?pairs[i] = [starti, endi]?。如果?pairs?的一個(gè)重新排列，滿足對(duì)每一個(gè)下標(biāo)?i?（?1 <= i < pairs.length?）都有?endi-1 == starti?，那么我們就認(rèn)為這個(gè)重新排列是?pairs?的一個(gè)?合法重新排列?。

請(qǐng)你返回?任意一個(gè)?pairs?的合法重新排列。

注意： 數(shù)據(jù)保證至少存在一個(gè)?pairs?的合法重新排列。

示例 1：

輸入：pairs = [[5,1],[4,5],[11,9],[9,4]]
輸出：[[11,9],[9,4],[4,5],[5,1]]
解釋：
輸出的是一個(gè)合法重新排列，因?yàn)槊恳粋€(gè) 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]]
解釋：
輸出的是一個(gè)合法重新排列，因?yàn)槊恳粋€(gè) endi-1 都等于 starti 。
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
重新排列后的數(shù)組 [[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]]
解釋：
輸出的是一個(gè)合法重新排列，因?yàn)槊恳粋€(gè) endi-1 都等于 starti 。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2

提示：

• 1 <= pairs.length <= 10^5
• pairs[i].length == 2
• 0 <= starti, endi <= 10^9
• starti != endi
• pairs?中不存在一模一樣的數(shù)對(duì)。
• 至少?存在?一個(gè)合法的?pairs?重新排列。

---

解法 歐拉路徑+DFS

如果我們把數(shù)組 $pairs$ 中出現(xiàn)的每個(gè)數(shù)看成一個(gè)節(jié)點(diǎn)，$({\text{start}}_i,{\text{end}}_i)$ 看成從 ${\text{start}}_i$ 到 ${\text{end}}_i$ 的一條有向邊，那么 $pairs$ 的一個(gè)合法排列就對(duì)應(yīng)著：

• 從節(jié)點(diǎn) $\text{pairs}[0][0]$ 開始；
• 依次經(jīng)過 $\text{pairs}[0][1],\text{pairs}[1][1],?,\text{pairs}[n?1][1]$

的一條路徑，其中 $n$ 是數(shù)組 $pairs$ 的長(zhǎng)度。這條路徑經(jīng)過了圖上的每一條邊恰好一次，是一條「歐拉通路」，因此我們的目標(biāo)就是找出圖上的任意一條歐拉通路。

對(duì)于本題而言，首先需要找到歐拉通路的起始節(jié)點(diǎn)：

• 如果圖中所有節(jié)點(diǎn)的入度和出度都相等，那么從任意節(jié)點(diǎn)開始都存在歐拉通路；
• 如果圖中存在一個(gè)節(jié)點(diǎn)的出度比入度恰好多 $1$ ，另一個(gè)節(jié)點(diǎn)的入度恰好比出度多 $1$ ，那么歐拉通路必須從前一個(gè)節(jié)點(diǎn)開始，到后一個(gè)節(jié)點(diǎn)結(jié)束。
• 除此之外的有向圖都不存在歐拉通路。

本題保證了至少存在一個(gè)合法排列，因此圖已經(jīng)是上述的兩種情況之一。當(dāng)我們確定起始節(jié)點(diǎn)后，就可以使用DFS求解歐拉通路了。如果我們得到的歐拉通路為：
$$v_1,v_2,v_3,?,v_n,v_{n+1}$$
那么 $[[v_1,v_2],[v_2,v_3],?,[v_n,v_{n+1}]]$ 就是一個(gè)合法排列。

class Solution {
public:vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {// 存儲(chǔ)圖unordered_map<int, vector<int>> edges;// 存儲(chǔ)入度和出度unordered_map<int, int> deg;for (const auto& p: pairs) {edges[p[0]].push_back(p[1]);++deg[p[0]], --deg[p[1]];}// 深度優(yōu)先搜索（Hierholzer算法）求解歐拉通路vector<vector<int>> ans;function<void(int)> dfs = [&](int u) {while (!edges[u].empty()) {int v = edges[u].back();edges[u].pop_back(); // 刪除一條邊dfs(v);ans.push_back({u, v});}};     // 尋找起始節(jié)點(diǎn)for (const auto& [x, occ]: deg) // 如果有節(jié)點(diǎn)出度比入度恰好多 1，那么只有它才能是起始節(jié)點(diǎn)if (occ == 1) {dfs(x);break;}if (ans.empty()) dfs(pairs[0][0]);reverse(ans.begin(), ans.end());return ans;}
};

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ ，其中 nnn 是數(shù)組 $pairs$ 的長(zhǎng)度。圖中有不超過 $n+1$ 個(gè)節(jié)點(diǎn)和 $n$ 條邊，因此求解歐拉通路需要的時(shí)間為 $O(n)$ 。
• 空間復(fù)雜度：$O(n)$ ，即為存儲(chǔ)圖需要使用的空間。

求解歐拉通路使用DFS，可以參考「OI Wiki — 歐拉圖」 ，一般使用 $\text{Hierholzer}$ 算法求解歐拉通路，與歐拉回路或歐拉通路有關(guān)的題目：

• 「332. 重新安排行程」
• 「753. 破解保險(xiǎn)箱」