圖形演算法-關節點(articulation point)

關節點的判斷演算法

(1)若點p是深度優先搜尋樹的根節點，因為深度優先搜尋樹的子樹之間不會相連，會相連就會屬於同一子樹，所以點p只要有兩個以上的子樹，則點p就是關節點(articulation point)。

(2)若點p不是深度優先搜尋樹的根節點，點p的每個子孫都有back edge可以連到點p的祖先(不含點p)，該點就不是關節點(articulation point)，若有一個子孫沒有back edge，該點就是關節點(articulation point)。

使用程式判斷圖形的邊為back edge

深度優先搜尋走訪過程中點的走訪順序可以標記在陣列v中，可以使用陣列v來判斷是否有back edge的存在，back edge表示在深度優先搜尋走訪順序較晚的點，有邊連結到走訪順序較早的點，這些邊被稱為back edge。

(一)找出關節點

給定最多100個節點以內的無向圖，每個節點編號由0開始編號，且節點編號皆不相同，相同起點與終點的邊只有一個，請找出圖形中的關節點。

輸入說明

輸入正整數n與m，表示圖形中有n個點與m個無向邊，接下來有m行，每個邊有兩個數字，兩個數字為邊的兩端點節點編號，保證節點編號由0到(n-1)。

輸出說明

輸出關節點的個數與節點編號。

範例輸入

6 8

0 1

0 2

0 3

0 4

1 2

2 3

2 5

3 4

範例輸出

1

2

(a)解題想法

利用深度優先搜尋演算法(DFS)傳入兩個參數p與i，p為i的雙親，深度優先搜尋過程中標記每個節點拜訪順序到陣列v，使用另一個陣列up，表示子孫可以經由back edge拜訪的最高祖先，遞迴呼叫下一層時，使用參數i與target，i為target的雙親，分成以下兩種情形。

(1)若p等於i，表示點i是根節點，則點i的子樹只要兩個以上就是關節點。

(2)若點i不是根節點，若target等於p表示回到祖父母節點，不是back edge，否則target不等於p，若v[target]顯示已經拜訪過且up[target]小於v[i]，則邊(i,target)為back edge，若點i有一個子孫沒有back edge，也就是找到一個子孫節點target，up[target]大於等於v[i]，則點i就是關節點。

(二)找出關鍵的路口

給定最多100個節點以內的無向圖，每個節點名稱由字串組成，且節點名稱皆不相同，相同起點與終點的邊只有一個，請找出圖形中的關節點。

輸入說明

輸入正整數n與m，表示圖形中有n個點與m個無向邊，接下來有m行，每個邊有兩個節點名稱，兩個節點名稱為邊的兩端點節點名稱。

輸出說明

輸出關節點的個數與節點名稱。

範例輸入

6 8

Ax Bx

Ax Cx

Ax Dx

Ax Ex

Bx Cx

Cx Dx

Cx Fx

Dx Ex

範例輸出

1

Cx

(a)解題想法

利用深度優先搜尋演算法(DFS)傳入兩個參數p與i，p為i的雙親，深度優先搜尋過程中標記每個節點拜訪順序到陣列v，使用另一個陣列up，表示子孫可以經由back edge拜訪的最高祖先，遞迴呼叫下一層時，使用參數i與target，i為target的雙親，分成以下兩種情形。

(1)若p等於i，表示點i是根節點，則點i的子樹只要兩個以上就是關節點。

(2)若點i不是根節點，若target等於p表示回到祖父母節點，不是back edge，否則target不等於p，若v[target]顯示已經拜訪過且up[target]小於v[i]，則邊(i,target)為back edge，若點i有一個子孫沒有back edge，也就是找到一個子孫節點target，up[target]大於等於v[i]，則點i就是關節點。