Embedded Files
關節邊(articulation edge)又可以稱為橋(bridge)
在無向連通圖中找尋橋(bridge)，橋(bridge)表示從圖中移除這個邊會形成無法連通的圖，而若圖形表示交通網路圖，這些橋(bridge)就是不可以取代的邊，一定要能夠維持能順暢通過這些橋，不然圖形上某些點就無法到達。其實與關節點程式碼，如下表，只要改一個地方，就可以改成找尋橋的程式碼。
想想看
為何橋(bridge)需要「up[target] > v[i]」，而非「up[target] >= v[i]」？
找出橋
給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，相同起點與終點的邊只有一個，請找出圖形中的橋(bridge)。
輸入說明
輸入正整數n與m，表示圖形中有n個點與m個無向邊，接下來有m行，每個邊有兩個數字，兩個數字為邊的兩端點節點編號，保證節點編號由0到(n-1)。
輸出說明
輸出橋(bridge)的個數與邊的兩端點節點編號。
範例輸入
6 8
0 1
0 2
0 3
0 4
1 2
2 3
2 5
3 4
範例輸出
1
2 5
(a)解題想法
利用深度優先搜尋演算法(DFS)傳入兩個參數p與i，p為i的雙親，深度優先搜尋過程中標記每個節點拜訪順序到陣列v，使用另一個陣列up，表示子孫可以經由back edge拜訪的最高祖先，遞迴呼叫下一層時，使用參數i與target，i為target的雙親。
若target等於p表示回到祖父母節點，不是back edge，否則target不等於p，若v[target]顯示已經拜訪過且up[target]大於v[i]，up[target]表示點i的子孫點target，能夠拜訪的最高祖先不能到v[i]，只能到深度優先搜尋拜訪順序在v[i]後面的點，所以刪除邊(i,target)，就會形成圖形不連通，所以邊(i,target)是橋。
為何在橋(bridge)時，若up[target]等於v[i]，則邊(i,target)不能算是橋，因為刪除邊只會刪除該邊，但關節點是點，刪除點時會順便刪除所有該點連結出去的邊，若up[target]等於v[i]，刪除邊(i,target)後圖形還可以連通，就不符合橋的定義，所以只能使用「up[target]大於v[i]」而非「up[target]大於等於v[i]」。
(b)程式碼
(c)程式結果預覽
按下「執行->編譯並執行」，結果顯示在螢幕如下。
Page updated
Google Sites
Report abuse