Data Structure第七次作業講解
期中以來，有不少同學向我反應代碼寫的慢、正确率不高等問題。由于OS已經爆炸閑的沒事幹 是以我決定将自己原來寫的代碼重構重構，并整理成部落格附上整個思路的講解。首先，我必須申明，部落格所寫的東西，是供想提升自己代碼水準，理清寫碼思路的同學用的。我希望同學們能夠明白：作為一個考試分數占 80% 的學科，抄襲他人代碼完成作業不是白賺了那 20% 的分數，而是失去了一次良好的練兵的機會（從本次開始，文章中給出的代碼均已送出評測，抄襲需謹慎）。其次，個人所寫代碼隻是提供一個寫碼、思考問題的思路，并不代表題目的唯一解法，更不代表最優解法沒有送出到課程網站上測試，隻在本地通過測試資料，甚至可能有bug噢。我希望我的代碼能夠起到抛磚引玉的作用，能夠讓同學對課上内容有更深刻的了解，寫代碼時能夠有更多更好的想法。最後，我希望同學們在完成作業的同時，能夠對自己的代碼進行複雜度的分析。資料結構的使用，往往離不開對性能的限制，是以，掌握複雜度的分析也是這門課程重要的一環。
本文中所有的代碼風格皆采取 OO 的标準，同時作者也希望同學們能夠以這種标準限制自己，這樣也會友善助教 debug。簡單來說，大緻限制如下：
1、符号後帶空格。
2、大括号不換行。
3、if、while、for 等括号兩端應該帶空格，并且一定要用大括号括起來。
4、一行不要寫過多字元（不超過60），較長的判斷可以換行處理。
5、縮進為 4 個空格，不同層次間要有合适的縮進。
6、一行隻聲明一個變量，隻執行一個語句。
采取了dhy大佬的意見，決定新添加這個欄目，對本次代碼中使用到的基礎的一些資料結構或是函數進行一些簡單的講解，便于大家的使用和了解。
快速讀入是比較好用的一種讀入的寫法，我這裡的實作是通過循環讀入直到得到下一個數字，在具體的題目中也可以根據自己的需要對循環的條件和結束條件做更改來讀入字元串等。（由于隻涉及到簡單循環，這裡不作更深入的講解）。切忌不經思考和了解就使用，容易出現讀入死循環等問題。
在解決需要建邊（如：樹、圖）相關的問題時，比較友善的一種資料結構。在第一道題中用到了類似的結構，是以我們在這裡做個講解。
如此圖所示，我們新加入編号為 3 的邊
初始狀态 e[1] = {2, 0} （前面為to，後面為nxt）
e[2] = {3, 1}
h[1] = 2
這時我們建立 e[3] = {4, h[1]} 即 {4，2}
再令 h[1] = 3
那麼周遊的時候我們可以通過 h[1] 找到 e[3]，再通過 e[3].nxt 找到 e[2], 再通過 e[2].nxt 找到 e[1]，就獲得了完整的邊的資訊。
一種多用在解決集合關系中的算法，實作 kruskal 所需要的工具。
簡單來講，就是維護一個 prt 數組。
當 prt[i] = i 時，代表這個點就是集合的代表元素。否則一直往上找到一個這樣的點。
連接配接兩個點 x，y 就是分别找到他們的代表元素 f1 和 f2
如果 f1 == f2 ，則代表兩個點已經在同一集合中，不需要更改并查集
否則令 prt[f1] = f2 ，完成建邊。
一種最短路算法，思路簡單暴力，實作簡單，複雜度優秀（如果沒有被資料針對的話）
整體架構大緻如下：
我們用一個 vst 數組記錄點在不在隊列中。
如果一個點的最短路被更新時不在隊列中，就把它加入隊列中
本質上就是對暴力BFS的優化 是不是很簡單
【問題描述】
給定一個無向圖和一個圖頂點，程式設計輸出該圖删除給定頂點前後按深度優先周遊及廣度優先周遊方式周遊的圖頂點序列。
給定的無向圖和圖頂點滿足以下要求：
1、無向圖的頂點個數n大于等于3，小于等于100，輸入時頂點編号用整數0～n-1表示；
2、無向圖在删除給定頂點前後都是連通的；
3、無論何種周遊，都是從編号為0的頂點開始周遊，通路相鄰頂點時按照編号從小到大的順序通路；
4、删除的頂點編号不為0。
【輸入形式】
先從标準輸入中輸入圖的頂點個數和邊的個數，兩整數之間以一個空格分隔，然後從下一行開始分行輸入每條邊的資訊（用邊兩端的頂點編号表示一條邊，以一個空格分隔頂點編号，邊的輸入次序和每條邊兩端頂點編号的輸入次序可以是任意的，但邊不會重複輸入），最後在新的一行上輸入要删除的頂點編号。
【輸出形式】
分行輸出各周遊頂點序列，頂點編号之間以一個空格分隔。先輸出删除給定頂點前的深度優先周遊頂點序列和廣度優先周遊頂點序列，再輸出删除給定頂點後的深度優先周遊頂點序列和廣度優先周遊頂點序列。
【樣例輸入】
9 10
0 1
0 2
1 4
1 3
1 8
8 6
3 6
7 2
7 5
5 2
3
【樣例輸出】
0 1 3 6 8 4 2 5 7
0 1 2 3 4 8 5 7 6
0 1 4 8 6 2 5 7
0 1 2 4 8 5 7 6
【樣例說明】
輸入的無向圖有9個頂點，10條邊（如下圖所示），要删除的頂點編号為3。
從頂點0開始，按照深度優先和廣度優先周遊的頂點序列分别為：0 1 3 6 8 4 2 5 7和0 1 2 3 4 8 5 7 6。删除編号為3的頂點後，按照深度優先和廣度優先周遊的頂點序列分别為：0 1 4 8 6 2 5 7和0 1 2 4 8 5 7 6。
按照題目要求從 0 開始進行 dfs 和 bfs
這個題要求周遊按照編号的順序，是以我們用鄰接矩陣來存再枚舉可以自動滿足這個要求
除此之外我們需要一個vst數組來記錄通路了哪些點
然後就正常進行 bfs 和 dfs 即可
由于使用了鄰接矩陣，每個點都周遊了一次别的點， 複雜度是 O(n²) 的
老張和老王酷愛爬山，每周必爬一次香山。有次兩人為從東門到香爐峰共有多少條路徑發生争執，于是約定一段時間内誰走過對方沒有走過的路線多誰勝。
給定一線路圖（無向連通圖，兩頂點之間可能有多條邊），程式設計計算從起始點至終點共有多少條獨立路徑，并輸出相關路徑資訊。
注：獨立路徑指的是從起點至終點的一條路徑中至少有一條邊是與别的路徑中所不同的，同時路徑中不存在環路。
圖的頂點按照自然數（0,1,2,...,n）進行編号，其中頂點0表示起點，頂點n-1表示終點。從标準輸入中首先輸入兩個正整數n,e，分别表示線路圖的頂點的數目和邊的數目，然後在接下的e行中輸入每條邊的資訊，具體形式如下：
說明：第一行<n>為圖的頂點數,<e>表示圖的邊數；第二行<e1> <vi1> <vj1>分别為邊的序号（邊序号的範圍在[0,1000）之間，即包括0不包括1000）和這條邊的兩個頂點（兩個頂點之間有多條邊時，邊的序号會不同），中間由一個空格分隔；其它類推。
輸出從起點0到終點n-1的所有路徑（用邊序号的序清單示路徑且路徑中不能有環），每行表示一條由起點到終點的路徑（由邊序号組成，中間有一個空格分隔，最後一個數字後跟回車），并且所有路徑按照字典序輸出。
6 8
1 0 1
2 1 2
3 2 3
4 2 4
5 3 5
6 4 5
7 0 5
8 0 1
1 2 3 5
1 2 4 6
7
8 2 3 5
8 2 4 6
樣例輸入構成的圖如下：
輸出的第一個路徑1 2 3 5，表示一條路徑，先走1号邊(頂點0到頂點1)，然後走2号邊(頂點1到頂點2)，然後走3号邊(頂點2到頂點3)，然後走5号邊(頂點3到頂點5)到達終點。
輸出所有從 0 到 n - 1 的簡單路徑，并且還要按照字典序。
顯然一個 bfs 或者 dfs 我們就能得到所有這樣的路徑，但這樣終究有點麻煩。
我們隻要對邊排好序，其實通路到可行的路徑自動就是一個字典序的。
之後隻要在 dfs 過程中用棧來維護答案就可以了。
由于涉及到路徑的複制，且路徑數随邊數變化較大，複雜度可以非常大，但是由于邊數限制，這種做法沒有問題。
北航主要辦公科研樓有新主樓、逸夫樓、如心樓、辦公樓、圖書館、主樓、一号樓等等;。北航網絡中心計劃要給相關建築物間鋪設光纜進行網絡連通，請給出用料最少的鋪設方案。
編寫程式輸入一個辦公區域分布圖及建築物之間的距離，計算出用料最少的鋪設方案（隻有一組最優解，不用考慮多組解)。要求采用Prim或Kruskal算法實作。
辦公區域分布圖的頂點（即建築物）按照自然數（0，1，2，n-1）進行編号，從标準輸入中首先輸入兩個正整數，分别表示線路圖的頂點的數目和邊的數目，然後在接下的行中輸入每條邊的資訊，每條邊占一行，具體形式如下：
...
即頂點vi和vj之間邊的權重是weight，邊的編号是id。
輸出鋪設光纜的最小用料數，然後另起一行輸出需要鋪設的邊的id，并且輸出的id值按照升序輸出。
6 10
1 0 1 600
2 0 2 100
3 0 3 500
4 1 2 500
5 2 3 500
6 1 4 300
7 2 4 600
8 2 5 400
9 3 5 200
10 4 5 600
1500
2 4 6 8 9
樣例輸入說明該分布圖有6個頂點，10條邊；頂點0和1之間有條邊，邊的編号為1，權重為600；頂點0和2之間有條邊，權重為100，其它類推。其對應圖如下：
經計算此圖的最少用料是1500，可以使圖連通，邊的編号是2 4 6 8 9。其對應的最小生成樹如下：
求最小生成樹
出于簡單，我們當然使用 kruskal 實作這道題
同時為了實作這道題，我們需要用到并查集（見前文）。
複雜度是 O(mlogm)，即邊排序的複雜度。
編寫一個程式實作北京地鐵最短乘坐（站）線路查詢，輸入為起始站名和目的站名，輸出為從起始站到目的站的最短乘坐站換乘線路。注：1. 要求采用Dijkstra算法實作；2）如果兩站間存在多條最短路徑，找出其中的一條就行。
檔案bgstations.txt為資料檔案（可從課程網站中課程資訊處下載下傳），包含了北京地鐵的線路及車站資訊。其格式如下：
<地鐵線路總條數>
<線路1> <線路1站數>
<站名1> <換乘狀态>
<站名2> <換乘狀态>
<線路2> <線路2站數>
說明：檔案第一行為地鐵總線路數；第二行第一個數為某條地鐵線線号（如，1為1号線），第二個數為該條地鐵線的總站數（如1号線共有23站），兩數之間由一個空格分隔；第三行兩個資料分别為地鐵站名及換乘狀态（0為非換乘站，1為換乘站），兩資料間由一個空格分隔；以下同，依次為該線地鐵其它站資訊。在一條線路資訊之後是下條地鐵線路資訊，格式相同。若某條地鐵線為環線，則首站與末站資訊相同（如北京地鐵2号線，首站資訊“西直門 1” ，末站資訊為“西直門 1”）。例如本題提供的bgstations.txt檔案（可從課程網站中課程資訊處下載下傳）内容如下：
13
1 23
蘋果園 0
古城 0
八角遊樂園 0
八寶山 0
玉泉路 0
五棵松 0
萬壽路 0
公主墳 1
軍事博物館 1
木樨地 0
南禮士路 0
複興門 1
西單 1
2 19
西直門 1
積水潭 0
鼓樓大街 1
在北京地鐵的背景下，用 dijkstra 實作最短路并且将路徑輸出。
其實并沒有用 dijkstra 而是用了 SPFA，具體見上文。
這個題似乎存在不是換乘站但是同時在兩條線路上的點，但是由于不涉及到測試資料，這裡就不考慮了因為考慮了我也錯了
真要考慮的話，可能需要使用分層圖來實作這道題，這就留給同學們自行了解了。
大體思路是利用鍊式前向星從 2 開始編号，異或得到相反邊的性質來儲存整個路徑，最後處理輸出。
最短路是用 SPFA 實作的，整個題目不簡單，請仔細閱讀代碼并深入思考。
複雜度是 SPFA 的複雜度，會随着圖的性質變化， 最壞是 O(VE) //點集 * 邊集
大巴黎，咚咚咚