描述
César 是個缺乏時間與距離觀念的人，要從一個地方到另一個地方時，往往會選擇最遠的那條路，César 的朋友為了打發時間，決定開發一個程式，計算從 César 的家裡出發，最遠可以到達何處。給定 \(n\) \((1 < n ≤ 100)\) 點以及數個有向的道路（並且這些道路不構成環），若 César 的家位於點 \(s\) \((1 ≤ s ≤ n)\)，問 César 可以走的最遠距離以及最終抵達的地點（取編號最小）為何。
思路
第一層
直覺上，由於本題可以視為求解有向無環無權圖的最長路徑問題，直接使用深度優先搜索（DFS）或廣度優先搜索（BFS）就可以得到答案，但是絕大多數題目都沒有這麼簡單，而本題也不例外，不優化會得到 TLE 認證。
第二層
欲求解圖的最長路徑，我們必須要檢查所有邊（見證明：命題一），由於有向無環無權圖是圖，因而不可避免地適用該規則，有鑑於此，我們將目標設為盡量避免重複檢查的已檢查過的邊。令 \(G = (V, E)\) 為有向無環無權圖，\(V = \{1, 2, \dots, n\}\) 且 \(p, q \in V\) ，當 \(p\) 和 \(q\) 同時出現時，\(p \neq q\)，\(E\) 為題目給定的道路的集合，另外，以 \(p \xrightarrow{} q\) 表示 \(p\) 可到達 \(q\) 。
策略一：提前放棄
假設 \(p \xrightarrow{} q\)，則這些可到達的路徑中必有最長的，換而言之，如果第一次自 \(p\) 出發，抵達 \(q\) 的長度為 \(l_1\)，第二次自 \(p\) 出發，抵達 \(q\) 的長度為 \(l_2\)，若 \(l_1 \geq l_2\)，表示第二次抵達 \(q\) 後就可以提前放棄，因為不可能比第一次更長，如果還沒悟道的話，使 \(l\) 為自 \(q\) 出發可到達的最長距離，則 \(l_1 + l \geq l_2 + l\) 在 \(l_1 \geq l_2\) 的條件下必然成立，這就是真相。
策略二：不走相同路
若 \(V' = \{v' \in \{v \in V \:\colon\: (v, q) \notin E\} \:\colon\: p \xrightarrow{} v'\} = \{r_1, r_2, \dots, r_{|V'|} \}\)，如果自 \(p\) 出發，抵達 \(r_1\) 的最長距離為 \(l_1\)，自 \(p\) 出發，抵達 \(r_2\) 的最長距離為 \(l_2\)，依此類推，可以知道自 \(p\) 出發可到達的最長距離為 \(l_{max} = max(l_1, l_2, \dots, l_{|V'|})\)，當知道 \(l_{max}\) 後，倘若再次抵達 \(p\) ，就不需繼續檢查以前已經走過的邊，直接把當前距離加上 \(l_{max}\) 即可得到答案。
策略三：雙修
接下來展示同時使用兩種策略的好處，假設輸入如下：
1 | 11 |
畫出對應的圖，可以得到：
不難看出可以構成六條路徑：
\[ \begin{align*} A &= (1, 2, 3, 8, 9) \\ B &= (1, 2, 3, 8, 10, 11) \\ C &= (1, 4, 5, 6, 8, 9) \\ D &= (1, 4, 5, 6, 8, 10, 11) \\ E &= (1, 7, 8, 9) \\ F &= (1, 7, 8, 10, 11) \end{align*} \]
現在按 DFS 的順序檢查，這裡讓我偷個懶，只關注跟 \(8\) 相關的距離就好。
| 檢查的邊 | \(1\) 到 \(8\) 的最長距離 | 自 \(8\) 出發的最長距離 | 終點 | 狀態 |
|---|---|---|---|---|
| \((1, 2), (2, 3), (3, 8), (8, 9)\) | \(3\) | \(1\) | \(9\) | 完成 \(A\) |
| \((8, 10), (10, 11)\) | \(3\) | \(2\) | \(11\) | 完成 \(B\) |
| \((1, 4), (4, 5), (5, 6), (6, 8)\) | \(4\) | \(2\) | \(11\) | 符合策略二，完成 \(C\)、\(D\) |
| \((1, 7), (7, 8)\) | \(4\) | \(2\) | \(11\) | 符合策略一，完成 \(E\)、\(F\) |
透過雙修，在僅僅檢查輸入的所有邊一次後，就可以得到自 \(1\) 出發可到達的最長距離為 \(6\)，且終點為 \(11\)。
結論
DFS 或 BFS 配上雙修可以保證在 \(\theta(|E|)\) 的時間複雜度和 \(\theta(n)\) 的空間複雜度上解決有向無環圖（無權重或全部正權重）的最長路徑問題，並且易見其正確性，實際解題中，實現一種策略即可，兩種都做僅為錦上添花。
備註
- 雖說 DFS 和 BFS 都可以實現策略一、二甚至雙修，不過 DFS 比較省心。
- 每一點都需要紀錄相關數值，畢竟我們不會知道只需記錄哪些點。
- 令 \(v'' \in \{v' \in \{v \in V \:\colon\: (v, q) \notin E\} \:\colon\: s \xrightarrow{} v'\}\)，\(P\) 為 \(G\) 中所有滿足 \(s \xrightarrow{} v''\) 的路徑的集合，\(E'\) 為構成 \(P\) 中所有路徑所需的邊的集合，準確來說，雙修只需檢查 \(E'\) 中的所有邊一次即可，不過因為 \(E' \subseteq E\)，所以 \(|E'|\) 的上下界與 \(|E|\) 相同，都為 \(\left[1, \frac{n(n-1)}{2}\right]\)。
- 如果覺得文中缺乏 \(\forall\) ，請自行腦補。
證明
命題一：求解圖的最長路徑問題，必須檢查所有邊。
令 \(G = (V, E)\) 且 \(s, e \in V\)，\(t \notin V\)，定義 \(s\) 為起點，\(e\) 為 \(G\) 中以 \(s\) 為起點的最長路徑的終點。構造 \(G' = (V \cup \{t\}, E \cup \{(e, t)\})\)，假設不需檢查所有邊，那麼可以在不檢查 \((e, t)\) 的情況下，得知 \(t\) 為 \(G'\) 中以 \(s\) 為起點的最長路徑的終點，但因 \((e, t)\) 為 \(G'\) 中唯一一條與 \(t\) 相連的邊，所以要知道 \(t\) 為終點，必然要檢查 \((e, t)\)，與假設矛盾，故原命題得證。