Don’t Really Like How The Story Ends

題意：

有n個點，m個邊，現在要從1號邊開始求dfs序，問最少加多少邊可以是的dfs序是從1到n？

題解：

dfs序的過程中，不走到葉子節點我們是無法回溯的，這段路相當于一個鏈，所以我們可以用一個棧結果來存鏈上的點。
我們討論各種情況：

如果u與u+1正好相連，就直接搜索u+1，不需要多加邊

如果u存在一個相鄰的點x還未訪問，且u+1與u不相鄰，此時必須加邊，將u與u+1相連。因為按照dfs序，從u是要繼續向下dfs，如果不加邊就要遍歷點x，這樣dfs序就不連續了

如果u所有相鄰的點都被訪問了，u+1可以與u相連，也可以與棧內其他點連邊，此時一直讓u退棧，直到回到滿足條件1或條件2的節點

如果第三種情況一直退棧，棧空了，也沒有滿足1和2情況的節點，此時就必須加邊了，說明存在不連通部分，然后再繼續dfs序走

代碼：

代碼待補

總結

以上是生活随笔為你收集整理的E. Don‘t Really Like How The Story Ends(代码未补)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。